В декабре 1993 было записано третье демо «... From The Pagan Vastlands». Демо было выпущено в 1995 году Pagan Records, через год на CD в США (лейблом Wild Rags) и Европе (лейблом Nazgul's Eyrie). Выпуск третьего демо привёл к подписанию контракта с итальянской звукозаписывающей компанией Enthropy Records.

В 1994, по приглашению группы Mastiphal, «Нергал» сыграл на барабанах на альбоме Nocturnal Landscape. Однако в июле 1994 группа работала в студии над материалом для EP с предварительным названием «Moonspell Rites». Альбом в конечном итоге стал называться «And the Forests Dream Eternally» и был выпущен в тот же год Enthropy Records. Опять же, как дуэт «Нергал» и «Ваал», в декабре 1994 года, записали и лейбл Pagan Records выпустил первый альбом «Sventevith (Storming Near the Baltic)», совместно с клавишником Cezarem "Cezar" Augustynowiczem, основателем группы Christ Agony. «Seventevith» годом позже был выпущен компакт-диском на лейбле Enthropy Records. На альбом в первую очередь вдохновили языческие верования, обложка альбома — работа David Tierre (Dark Arts). Альбом был хорошо принят фанатами и критиками, в результате чего был заключён контракт с немецким лейблом Solistitium Records ещё на два полноценных альбома.

1996—2003

«Grom», первый альбом на новом лейбле, был выпущен в Польше Atratus Music в 1996 году, а записан был в декабре 1995 года. Обложка альбома украшена работой David Tierre (Dark Arts). Альбом записан в пограничном стиле между трэш- и блэк-металом, там также имеется женский вокал. На альбоме две песни на польском языке: «Grom» и «Lasy Pomorza».

В том же году, лидер группы «Нергал» начал своё обучение в Университете Гданьска на факультете филологии и истории. Однако это не помешало выпуску ещё одного альбома, названного «Pandemonic Incantations», в конце августа. Альбом был выпущен лейблами Novum Vox Mortis и Solistitium Records 2 марта 1998 года, а год спустя на итальянском лейбле Avantgarde Music. Обложка альбома и макет делается в сотрудничестве с «Marquisem», также был создан новый логотип для группы. Это был успех, в результате чего был заключён контракт с лейблом «Avantgarde Music». На альбоме была песня, озаглавленная «Chwala Mordercom Wojciecha», текст которой представляет собой реакцию на празднование 1000-летия Гданьска.

В результате раскола группу покинул «Мефисто» и в 1998 году в составе группы утвердился барабанщик «Inferno» (группа Azarath). 25 октября 1999 Avantgarde Music Label выпустил ещё один альбом группы «Satanica», записанный в студии Starcraft Stimulations (SS) на 60 дорожках. В песне «Decade Of Θerion» с этого альбома появляется фраза из телемитского ритуала «красного рубина» AПO ПANTOΣ KAKOΔAIMONOΣ, в свободном переводе означает защиту от вызываемых духов. Вскоре после выпуска альбома (в 1999 году) группа играла его несколько раз, в том числе в туре по Франции, Испании и Англии, вместе с такими группами, как Deicide (США), Rotting Christ (Греция), Ancient Rites (Бельгия) и Satyricon (Норвегия).

В 2000 году усилиями Metal Mind Productions группа выпустила на VHS концертную запись «Live Eschaton: The Art of Rebellion», записанную на концерте в Кракове 27 апреля 2000 г. И уже в августе в Люблине в сотрудничестве с поэтом и переводчиком Кшиштофом Азаревичем был выпущен новый альбом «Thelema.6». Альбом включал трек «Inauguration Of Scorpio Dome», вдохновлённый фильмом Кеннета Гнев «Lucifer Rising» 1972 года, и трек «Vinvm Sabbati» со ссылкой на формулу магического «Zos Kia Cultus» Остина Османа. Издатель в США был Olympic Records, в России — Irond Productions. Группа также подписала контракт с бразильской рекорд-компанией Moira Records. Также состоялось концертное турне, где Behemoth выступали с такими группами как Morbid Angel, The Crown, Dying Fetus.