Koldbrann был сформирован Mannevond в начале 2001 году с целью воплотить главное его желание - играть мрачный и уродливый блэк-металл в классических его традициях, то есть без электронных вставок, экзотических инструментов и прочего "мусора", как выражается Mannevond.

Когда в конце этого же года пришел гитарист Dragev, было решено записать первую демку. Но Dragev захотел уехать (и уехал). Ему скоро нашли замену в лице Kvass. И вот, без драммера, но полные желания играть, дуэт начал запись материала. Через некоторое время с ними связался драммер Fordervelse и предложил свои услуги. Его приняли, и не зря - его мастерство было достаточно велико, чтобы вывести банду на качественно новый уровень.

Июль 2002 год - Koldbrann записывают дебютную демку "Pre-Prod 2002" в собственной "студии" NekroTrygd, с Kjottring в качестве басиста. Название означало, что демка сия - лишь часть еще одной предстоящей демки. И наконец, чуть позднее, в количестве 500 копий зарелизен Demo CD.

Сие творение на электронном носителе было тепло встречено в норвежском и мировом андерграунде и получило в основном высокие оценки. Скопировано с Dark-World.ru. Это привело к подписанию контракта между группой и шотландским лейблом Desolate Landscapes (на один полноформатник), а позднее с норвежцами из Apocalyptic Empire Records (на 7" EP). В это время приходит сессионный басист Jonas и с ним Koldbrann отыгрывают свое первое живое шоу на фесте Legions of the North с другими известными норвежцами: Endsum, Grenjar, и Vidsyn. Спустя пару недель концерты в Pandemonium Metal Club (Осло), снова с Endsum. Группой поддержки на этих концертах были парни из Madder Mortem.

Декабрь 2002 года - релиз "Mislyder fra Det Nekrotiske Kammer" (выпущен в количестве всего нескольких копий и переиздаваться не будет).

В марте 2003 года Jonas заявил о своем уходе. General Kshatriya (Disiplin, ex-Myrkskog) и Mpress (Zeenon) вступают в состав в качестве "живых" музыкантов на второй гитаре и басу соответственно. В том же году вышел в свет дебютный альбом коллектива - "Nekrotisk Inkvisition". Работа была выпущена силами музыкантов в апреле тиражом в 333 копии, пронумерованные вручную.

Чуть позже Koldbrann удаётся заполучить контракт с лейблом Twilight Vertrieb, на котором в июне 2006 года вышла вторая полноформатная работа коллектива под названием "Moribund".