В ноябре 1998 года Аббат и Хорг приступили к записи нового альбома. На этот раз запись проходила в шведской студии «Abyss» Петера Тэгтгрена (Peter Tägtgren), который стал звукоинженером и продюсером группы. Тот факт, что Аббату пришлось писать всю музыку без участия Демоназа, не оказал большого влияния на стиль Immortal, поскольку и до этого большую часть музыки сочинял он. Аббат также попробовал самостоятельно писать тексты песен, однако в итоге отдал эту работу Демоназу. Пятый по счёту альбом группы был выпущен в феврале 1999 года под названием At the Heart of Winter. Новая работа музыкантов получила высокие оценки от критиков и за два года разошлась тиражом более 70 тысяч экземпляров. Группа впервые отошла от устоявшейся традиции и использовала на обложке изображение фантастического зимнего пейзажа вместо собственной фотографии, а также представила публике новый, более читаемый логотип Immortal.

В 1998 году группа также приняла участие в создании трибьют-альбома группы Darkthrone, для которого записала кавер-версию песни «To Walk the Infernal Fields». Альбом был выпущен под названием Darkthrone Holy Darkthrone лейблом Moonfog Productions.

1999—2003 Приход Искарии. Смена лейбла

Сразу после выхода At the Heart of Winter в 1999 году место постоянного басиста занимает Искария (Iscariah), игравший до этого в группе Enchanted. В мае Immortal отправляются в очередное турне, однако были вынуждены на середине прервать его из-за воспаления уха Аббата. Искария не имел опыта концертных выступлений, поэтому для него это турне стало серьёзным испытанием. Однако постоянное напряжение во время турне и поддержка участников Immortal позволили ему вскоре обрести уверенность в себе и почувствовать себя полноценным членом группы.

В октябре 1999 года и начале февраля 2000 года на студии Abyss музыканты записывают свой шестой полноформатный альбом, получивший название Damned in Black. Предварительные заказы на выпущенный в апреле альбом составили по разным данным 40-50 тысяч, а суммарные продажи превысили 100 тысяч экземпляров. Альбом также попал в немецкие чарты, а позднее удостоился норвежской музыкальной премии Alarmprisen в категории «Metal». После выхода Damned in Black группа отправилась в турне, посетив при этом Северную Америку.

Помимо Immortal музыканты занимались и другими проектами. Во время записи Damned in Black группа получила предложение принять участие в записи трибьют-альбома Mayhem. Музыканты согласились при условии, что они сами выберут композицию для исполнения. В итоге была выбрана песня «From the Dark Past» с альбома De Mysteriis Dom Sathanas. Трибьют-альбом под названием Originators of the Northern Darkness – A Tribute to Mayhem был выпущен в мае 2001 года лейблом Avantgarde Music. Хорг исполнял роль ударника на концертах шведской группы Pain в конце 2000 года. Искария являлся басистом группы Wurdulak и записал вместе с ними альбом Ceremony in Flames. Кроме этого, Хорг и Искария в союзе с гитаристом Frediablo положили начало группе Grimfist.

Damned in Black стал последним альбомом, вышедшем на лейбле Osmose Productions. Контракт на следующий альбом Immortal подписали с немецким лейблом Nuclear Blast. Сотрудники Osmose связали уход группы с возросшими финансовыми запросами музыкантов. Сами же музыканты причиной перехода на другой лейбл назвали недостаточные для дальнейшего развития группы возможности Osmose, в том числе отсутствие у лейбла дистрибьютора в США.

В сентябре 2001 года Immortal возвращаются в студию Abyss для записи седьмого альбома. Вышедший в феврале 2002 года Sons of Northern Darkness развеял опасения некоторых фанатов группы, боявшихся, что смена лейбла негативно скажется на музыке Immortal. Весной музыканты вместе с Vader, Hypocrisy и рядом других групп отправляются на европейский фестиваль-турне «No Mercy». В конце марта Искария по собственному желанию покидает группу. На замену ему приходит концертный басист группы Pain Сарот (Saroth), с которым Immortal продолжают концертные выступления на европейских и американских площадках в 2002 и 2003 годах.