Сесії проходили в "Garageland Studios", а вакансію ударника в той час займала драм-машина. Демо виявилося досить вдалим, і чутки про нього поширювалися в андеграунді зі швидкістю лісової пожежі.
У кінцевому підсумку "Stellae Trajectio" потрапила до рук представників "Wrong again records", які поспішили укласти з "Naglfar" контракт. У 1995-му вийшов дебютний альбом гурту, записаний у складі: Йенс Райден (вокал), Андреас Нільссон (гітара), Кристоффер Олівіус (бас), Морган Ханссон (гітара) і Матті Хольмгрена (ударні).
"Vittra" кілька нагадував творіння "Cradle of filth" і "Hecate enthroned", ось тільки музика була помелодічнее, ніж у вищезазначених колективів. У серпні 1997-го "Naglfar" знов опинилися в студії, де записали пару епічних композицій ("When autumn storms come" і "The Brimstone gate"). Обидві речі вмістилися на одному EP, який вийшов обмеженим тиражем. До речі, в створенні цих пісень брав участь новий барабанщик, Маттіас Гран. На початку 1998 року пройшли сесії другого альбому, "Diabolical", за видання якого взявся тільки що виник лейбл "WAR music".
На відміну від "Vittra" другий опус вийшов більш швидким і екстремальним, але в той же час на платівці була присутня фірмова шведська мелодійність. На підтримку диска "Naglfar" провели європейське турне в компанії з "Brutal truth", "Six feet under" і "Deicide", зустрічаючи скрізь теплий прийом з боку слухачів.
Наприкінці 2000-го команда провела пару тижнів у "Ballerina studio", витративши цей час на запис міні-альбому "Ex Inferis". У тому ж році склад групи покинув Морган Ханссон, який вирішив зав'язати з музичною кар'єрою, а його місце зайняв Маркус Норман з "Bewitched". Чергового полноформатніка шанувальникам "Naglfar" довелося чекати ще цілих три роки. Зате вони не справдилися у своїх очікуваннях і отримали прекрасний альбом, що поєднує агресивність старої блек-школи і сучасну продюсерську роботу.
У Європі "Sheol" вийшов на "New Hawen records", а в Північній Америці поширювався за допомогою "Century media". З останнім з цих лейблів музиканти потім налагодили більш тісний контакт і свій четвертий лонгплей з робочою назвою "Pariah" пообіцяли випустити на "CM" навесні 2005 року.