Svartmetallband startet opp av bergenseren Øystein G. Brun (gitar) i 1995. Brun hadde nettopp forlatt bandet Molested for å søke nye utfordringer. Til å begynne med kjørte Brun løpet alene i Borknagar, med hjelp av medlemmer fra band som Enslaved, Immortal, Arcturus, Gorgoroth og Ulver.

I 1998 begynte Borknagar for alvor å ta form som et band. Jens F. Rydland ble hentet inn som ekstra gitarist, Simen Hæstnes kom inn på vokal, mens Kai Kristoffer Lie (bass) og Grim (Erik Brødreskift, trommer) kompletterte bandet.

Like før bandet skulle reise på turné med Cradle Of Filth i 1998, sluttet de to sistnevnte. Lie ble ikke erstattet, og Hestnæs spilte bass i tillegg til å synge. Justin Graves fra Iron Monkey ble hyret inn som trommeslager på turneen.

Da bandet kort tid etter reiste videre til USA, ble Graves erstattet av Nick Barker fra Cradle of Filth (senere Dimmu Borgir).

På tampen av 1999 ble Asgeir Mickelson (Spiral Architect) med som ny permanent trommeslager, mens Lazare (Lars Nedland) fra Solefald kom med på keyboards. Etter utgivelsen av Quintessence (2000) sluttet Hestnæs for å bli med Dimmu Borgir. Ny vokalist ble svenske Vintersorg (Andreas Hedlund) fra Vintersorg og Otyg, mens Tyr (Jan Erik Torgersen) (eks Emperor) kom med på bass.