Bethzaida была образована в конце 1993 года гитаристом Андре Свеем (Andre Svee) и ударником Тержем Краболом (Terje Krabol). В феврале 1994 к ним присоединились басист Олаф Мальмин (Olav Malmin) и вокалист-фелйтист Ларс Рубен Хирш (Lars Ruben Hirsch).
За май того же года они записали свою первую демо ''Dawn''. Запись звучала довольно брутально и наглядно демонстрировала, что корни творчества группы лежат в Doom Metal и Death Metal 80-х годов в сочетании с более современными влияниями Black Metal. Всю эту композицию завершало новаторское использование флейты не только как инструмента для создания настроения, но как полноценного включения в основанную на риффах музыку.
Ещё один шаг в этом направлении был сделан в 1995 году, когда появилась ещё одна демо, ''Nine Worlds'', которая и привела к подписанию контракта с французской компанией Season Of Mist.Nine Worlds был выпущен в 1996 году. Этот альбом мгновенно завоевал Bethzada репутацию в андеграундных кругах. По словам Анны Свано (Ana Swanno) из журнала Close Up (основной шведский журнал, посвящённый Металлу), альбом ''Nine Worlds'' был ''лучшей норвежской вещью за многие годы''! ''Nine Worlds'' - работа зрелой группы, способной создавать настроение, используя брутальную музыку, писать интересные тексты и оригинально использовать флейту. После этой работы басист Сандберг (Sandberg) ушёл, а оставшиеся участники решили тоже взять перерыв.
В конце 1997 года Season Of Mist выпустила 5 демо-записей на специальном MCD под названием ''Prelude to Nine Worlds''. Этот MCD в форме молота Тора был выпущен ограниченным тиражом в 1500 копий, которые были мгновенно распроданы.
Bethzaida вновь собрались в 1997 году, только теперь роль басиста выполнял Том Валь (Tom Vahl). Их последний альбом, LXXVIII, был записан в марте 1998 года. Он получился даже лучше, в нём куда больше настроения и брутальности, чем на предыдущих пластинках. Некоторые журналисты даже сравнивают Bethzaida с современным смешением Voivod, Black Sabbath и некоторым трэш-командами, и это им даже идёт!
Кроме того, группа записала 4 трека для сплит CD со шведской Anata, специально для линии Season Of Mist WAR (War II Norway Vs Sweden). На этом диске часть Bethzaida состоит из двух песен, одна из них - кавер к композиции Anata, вторая - адаптация 'Epistel nr.30', песни о смерти, отраве и вине, написанной шведским композитором 18 века Карлом Майклом Беллманом (Carl Michael Bellman).
