"Tristania" была основана в 1996 году клавишником-программером Эйнаром Моэном, ударником Кеннетом Олссоном и поющим гитаристом Мортеном Веландом. Моэн и Веланд перед этим занимались хэви-металом в "Uzi suiside", но такая музыка им скоро надоела, и парочка организовала новый проект, сманив к себе коллегу по "Uzi" Олссона. С приходом басиста Руне Остерхуса и гитариста Андерса Хойвика Хидле первый состав окончательно сформировался. В мае 1997-го коллектив отправился в студию и произвел на свет первое демо. На всякий случай музыканты решили использовать также женский вокал и пригласили на сессии Вибеке Стене.
Изначально не планировалось вводить ее в состав, но в процессе записи оказалось, что голос Вибеке как нельзя лучше подходит для избранного "Тристанией" стиля, и вокалистка стала шестым членом команды. Демку разослали по лейблам, и спустя некоторое время пришло заманчивое предложение от "Napalm records". Пленку в срочном порядке перемикшировали, и в результате на свет появился MCD со скромным названием "Tristania". Релиз получил положительные отзывы в европейской прессе, а воодушевленные норвежцы принялись за создание полноценного альбома.
Спустя несколько месяцев Моэн и Веланд насочиняли достаточно материала, и уже в начале 1998-го "Widow's weeds" лежал на прилавках. По сути дела альбом представлял собой симфо-металл с элементами готики, дэта, блэка и классики. Кстати, в записи пластинки принимали участие два сессионщика – парень с "чистым" вокалом, Остен Бергой, и скрипач Пит Йохансен. Пробную вылазку за пределы родной Норвегии "Tristania" совершили в сторону Бельгии, где разогревали "Lacrimosa", а затем переместились в Австрию на фестиваль "Mind over matter". Уже после этого состоялось нормальное европейское турне в компании с "Haggard" и "Solefald". В 1999-м вышло второе полнометражное творение тристанийцев. Направленность группы в общем сохранилась, и лишь чуточку добавилось экстремальности.
Основная масса композиций была написана Моэном-Веландом, а на паре треков попробовал свои силы и Хидле. Помимо Бергоя и Йохансена в записи "Beyond the veil" принимал участие вокалист Ян Кеннет Барквед. Выпустив диск, группа отправилась хедлайнерствовать при поддержке "Trail of tears", "The sins of thy beloved" и "Antichrisis". Гастроли продолжились и на следующий год, причем наши викинги добрались даже до Мексики и США.
Все бы ничего, да только к концу 2000 года обстановка в коллективе накалилась, и Веланд хлопнул дверью. Пришлось роль второго основного сонграйтера взять на себя Хидле. Вместе с Моэном они набросали материал для третьего альбома, и весной 2001-го "Tristania" отправились во Францию записывать очередной шедевр. Поскольку Веланд был не только композитором, но и отвечал за экстрим-вокал, то надо было его кем-то заменить. Поэтому временно порычать в микрофон пригласили Ронни Торсена из "Trail of tears", в то время как "чистые" вокалы распределили между собой Бергой и Барквед.
Когда команда управилась с сессиями и вернулась в Норвегию, замена Веланду нашлась в лице Кьетила Ингебретсена. Заодно в состав группы был официально введен Остен Бергой, который стал полезным также в роли автора текстов. После выхода "World of glass" "Тристания" два года провела на гастролях, основательно исколесив Европу, а также посетив Мексику, Чили, Бразилию и Колумбию. Сделав небольшую паузу, весной 2004 года команда приступила к записи четвертого альбома.