Тогда они играли довольно классический heavy metal. К началу 2000-х в группе только два члена из оригинального состава Uzi... Это - Morten Veland (гитара, вокал), и Kenneth Olsson (барабаны). Осенью 1995 года Einar Moen (synth) примкнул к Uzi, и вскоре после этого группа изменила название на Tristania. В начале 1996 года в группе шли споры относительно музыкальных направлений и серьезности всего предприятия в целом. Через некоторое время Veland и Moen решили оставить группу, и начали записывать новый материал с помощью четырехдорожечного магнитофона и прихваченного из группы микрофона. После нескольких месяцев создания и разработки нового музыкального стиля, они оказались способны убедить Olsson-а, и возродить проект. Они решили сохранить прежнее имя, Tristania, которое придумал Veland.
"Это плод нашей фантазии, основанный на норвежском слове "trist", что означает "печаль", - рассказывает Андерс Хидле. - Это, конечно, наводит мысли о меланхолии, но на самом деле, насколько мне известно, такого слова нет ни в одном языке - мы сами его придумали!"

Музыка была теперь на стыке death / gothic metal. Осенью 1996 года Rune Osterhus (Бас) и Anders H. Hidle (Гитара) присоединились к группе. Группа работала на выпуск запланированного MCD в конце 1996, но судьба не подчиняется никаким планам. Он был отсрочен на несколько месяцев. Тем временем Tristania также была занята поисками вокалистки, которая могла бы спеть кое-что на MCD. Еще несколькими неделями прежде, чем они вошли в студию, они уже встречались с вокалисткой Vibeke Stene. Она примкнула к группе пока для репетиций но ее голос очень хорошо лег на их музыку. Tristania в итоге идут в студию в начале мая 1997 года. Выпуск CD самофинансировался и, прежде всего, предполагался как промо-материал, представляющий группу. Качество записи было неважное из за явного дефицита средств. Он был напечатан в количестве 500 экземпляров, которые были посланы компаниям записи, радиостанциям, журналам, в газеты и так далее. Множество копий было также продано в нескольких магазинах и самими членами группы, чтобы покрыть издержки на производство. Продажа пошла хорошо, так что они даже получили прибыль.
"На самом деле, - вспоминает Андерс, - мы записали всего лишь четыре песни. Это было обычное демо, 500 экземпляров, которые мы выпустили на свои деньги и разослали куда только можно: в музыкальные журналы, на радиостанции и так далее"
Женский вокал сработал очень хорошо, и Stene присоединилась к Tristania, как постоянный член. До сих пор музыка писалась тандемом Veland/Moen, но другие члены тоже начинают генерировать музыкальные идеи. Tristania отработали несколько живых концертов, и получили хорошую критику, и из средств массовой информации и от аудитории. Живьем Tristania использует секвенсоры, чтобы добиться того же звука, как и в студии. Как известно, Tristania подписали контракт с Napalm сразу на три полноразмерных альбома, и первым перевыпустили свой самиздатовский MCD снова. Блестящий мини-альбом, мощная смесь готического дума с эпическим блэком и призрачными, атмосферными мелодиями, и одновременно жесткая и брутальная, наподобие ранних My Dying Bride, Paradise Lost, Theatre of Tragedy. Этот CD был выпущен в 1997 на Napalm после того, как был ремикширован и продавался опять довольно хорошо. Он также получил хорошие отзывы во многих европейских журналах, включая Scream Mag. и Rock Hard.

В ноябре/декабре всё того же года был записан легендарный альбом 'Widow's Weeds'. Он замечателен по двум причинам. Во-первых, он делался во французской студии Sound Suite продюсером Терье Рефснесом (The Sins Of Thy Beloved, Obtained Enslavement, Dismal Euphony). Звук стал невероятно мощным и наполнился духом кельтской музыки, ибо обогатился ещё и скрипкой, партии которой исполнил Пит Йохансен. Во-вторых, "чистым" мужским вокалом на альбоме спел некто Остен Бергой. Альбом вышел в начале 1998 года и Tristania отправилась в свое первое настоящее турне - фирма снарядила в европейский тур вместе с Haggard и Solefald. Именно с этого момента имя группы стало регулярно появляться в прессе, причем в крайне положительном смысле. Например, всё тот же Rock Hard с ходу поставил альбому весьма высокий балл - 9 из 10! Этот новый альбом характеризуют как symphonic gothic metal, c элементами black metal. Это - шедевр в этом стиле. Как и другие группы из окрестностей Ставангера, и прежде всего Theatre Of Tragedy, Tristania торжествуют с их уникальной комбинацией готического дума и симфонического металла.
"Мы долго искали свой собственный саунд, свою изюминку, и, наконец, нашли ее. Уже с 'Widow's Weeds' - первый опыт Tristania со всеми этими нововведениями - о нас заговорили т о выделяющейся на фоне десятков и даже сотен других готик-групп. Тогда же наш стандартный набор инструментов пополнился скрипкой, и Пит Йохансен привнес в нашу музыку ирландские народные мотивы. На WW вы можете услышать настоящий кельтский звук!" - говорит гитарист Андерс Хидле.

Музыканты, включая скрипача, оперную вокалистку, басиста, гитариста, вокалиста, ударника объединяют свои невероятные способности в создании шедевра темной, готической меланхолии, помноженной на мощь ранних Paradise Lost , Gathering и соединенной с красотой Theatre of Tragedy и ранних Celestial Season. Это - уникальный неоклассический, величественный black doom metal! Затем последовало турне в поддержку альбома и выпуск мини-CD 'Angina', изменений в стилистике не последовало.
10-недель в студии Sound Suite с Терье Рефснесом в феврале/марте 1999 года принесли новый альбом 'Beyond The Veil'. По стилистике он мало чем отличается от предшественника, но по сути... По сути это более профессиональная работа, на которую ушло гораздо больше времени и денег. Кроме того в сочинении материала гораздо меньшую роль, чем прежде, играет Веланд. Теперь основную работу делает Моэн, остальным музыкантам тоже было дано право голоса. Так что о былом "авторском тандеме" Веланд/Моэн можно уже не говорить. Также следует отметить то, что группа использует куда больше электроники. Хотя по прежнему без работы не остался "скрипучий" Йохансен, а на время записи из добровольцев был даже сформирован небольшой хор. "Те кому понравился 'Widow's Weeds', не разочаруются и в этом в принципе оба диска не слишком сильно отличаются друг от друга, но определенный шаг в своем музыкальном развитии мы конечно же сделали. Это касается и чисто технических и организационных аспектов. Во-первых, на этот раз у нас было гораздо больше времени на запись, а во-вторых, в сочинении новых песен участвовали практически все члены группы, а не только Мортен и Эйнара, как раньше. 'Beyond The Veil' - это уже не просто gothic metal, а нечто большее. Для нас вообще очень важно разнообразие в музыке, и мы и в будущем будем стараться делать на этом основной упор. В следующий раз мы собираемся пригласить для записи массу сессионных музыкантов, особенно классических".

После выхода альбома состоялся солидный европейский тур. В ходе его среди прочих прошли совместные концерты с Tiamat и Anathema. Видя явный интерес публики к концертам группы Napalm Records решаются на выпуск официального видео 'Widow`s Tour'. Это концерт в Оберварте, Австрия, который они дали в ходе турне 1998 года, дополненный видеоклипом "Evenfall". Пара ремиксов и не вошедшая в альбом композиция были изданы на отдельном мини-CD 'Angina' (1999), который был издан в США с явно стратегическими намерениями...

24 июня 2000 года TRISTANIA участвует в BIEBOB Festival, и также участвует в других летних фестивалях в этом году, а конец 2000 года и начало нынешнего принесли им много неожиданностей. Было, например, решено сделать прорыв на американский континент. Однако вместо довольно обширных гастролей по США и Мексике пришлось ограничится четырёхдневным пребыванием в Лос Анджелесе с единственным выступлением на фестивале November To Dismember. Впечатление от мероприятия было смазано в целом - из-за отмены выступлений Venom и The Sins Of Thy Beloved. Из-за технических проблем Tristania тоже отыграла всего полчаса. К тому же Мортен Веланд крепко простудился и почти всё время просидел в отеле с температурой, глотая таблетки. Во всяком случае, первый шаг был сделан - их смогла увидеть хотя бы часть американских поклонников... После возвращения домой была продолжена работа над новым материалом, и в феврале все готовились отправиться в студию. Все, кроме Мортена Веланда, который покинул группу из-за обострения "непримиримых разногласий". 7 мая 2001 года точно известно - Morten Veland покинул TRISTANIA и не примет участия в записи нового альбома. Теперь его след можно отыскать в группе Elusive - в качестве гитариста. А поёт в этой группе Ян Кеннет Барквед, один из участников того самого студийного хора, что так печально и торжественно воет на 'Beyond The Veil'; организовал же Elusive в 1999 году другой "перебежчик" - Томми Олссон, покинув Theatre Of Tragedy. И если в упомянутом случае "отряд не заметил потери бойца", то с Мортеном всё было иначе. Ведь он и пел, и играл на гитаре, и долгое время являлся одним из ведущих авторов группы. Это замедлило, но не остановило работ над альбомом 'World of Glass', который выходит в сентябре! К 21 июля 2001 альбом был уже "отмастерён". Этот альбом уже в августе провозглашается альбомом месяца на Napalm Records.Написание музыки взяли на себя Моэн и Хидле. Партии брутального вокала проревел в Sound Suite Studio Ронни Торсен из Trail Of Tears, кроме того в группе появилось целых два (за одного битого двух небитых дают!) "чистоголосых" мужских вокалиста. Один из них - это всё тот же Ян Кеннет Барквед. Другой - тоже уже знакомый нам Остен Бергой, бэк-вокали