В 1992 году Мортен Веланд и Кеннет Ольссон основали хэви-металическую группу Uzi Suicide. В 1995 году к ним присоединился Эйнар Моэн, вскоре название было изменено на Tristania.Затем к группе примкнули бас-гитарист Рене Эстерхус и второй гитарист Андерс Хидле. В мае 1997 Tristania начали работать в студии над первым демо, названным Tristania. Во время записи в качестве сессионной вокалистки была приглашена Вибеке Стене, в итоге ставшая полноправным членом группы. Демо было разослано нескольким лейблам. В том же году Tristania подписали контракт с Napalm Records и после перезаписи издали демо как мини-альбом.
В ноябре-декабре того же года был записан дебютный альбом Widow’s Weeds (издан в начале 1998 года), получивший хорошую критику и выдвинувший Tristania в число наиболее ярких групп, строивших музыку на сочетании симфо-металического звучания и женского вокала. В качестве сессионных музыкантов в записи принимали участие Пит Юхансен (скрипка) и Эстен Бергёй (вокал). Успех позволил группе выступить на разогреве у Lacrimosa, а затем отправиться в европейское турне вместе с Haggard и Solefald. Видео с концерта в Оберварте (Австрия) было издано Napalm Records как Widow`s Tour (вместе с клипом на песню «Evenfall»).
Второй альбом Beyond the Veil был выполнен в одной манере с первым, и опять в записи участвовали Йохансен и Бергёй. В 1999 году Tristania отыграли два европейских турне (одно при поддержке The Sins of Thy Beloved, Trail of Tears и Antichrisis, второе вместе с Tiamat и Anathema) и выступили на Wacken Open Air, а в следующем году в первый раз выступили в Америке.
Если во время работы над Widow’s Weeds основная часть материала была написана Веландом при участии Моэна, то на Beyond the Veil роль Веланда уменьшилась. Личные и творческие разногласия привели к тому, что в 2000 году, уже после начала работы над третьим альбомом, Веланд покинул группу и вскоре создал собственный проект — Sirenia.
Несмотря на уход Веланда, в 2001 году Tristania выпустили третий альбом World of Glass. Музыка в основном была написана Хидле, вокалистом на постоянной основе стал Бергёй. На World of Glass Tristania впервые записали кавер-версию (песня «Modern End», принадлежащая группе Seigmen). Постоянным гроул-вокалистом стал Хьетиль Ингебретсен из группы Blindfolded. В рецензиях на альбом критиками было отмечено увеличение доли электронной музыки и отсутствие наблюдавшейся на ранних записях меланхоличности. В работе принимали участие четыре вокалиста, в том числе приглашённый для исполнения партий гроула Ронни Торсен из Trail of Tears. Пластинка была записана во французской студии Sound Suite.
После того, как истёк контракт на три альбома с Napalm Records, Tristania заключили контракт с другим немецким лейблом SPV/Stemhammer, и в 2005 году, спустя четыре года после World of Glass, появился альбом Ashes, сохранивший традиционное готик-металическое звучание. Tristania по-прежнему использовала три разных вокала — женское сопрано Вибеке, чистый мужской вокал Эйстена и гроул Хьетиля. После выхода Ashes в составе группы произошёл ряд перемен: сначала впервые после ухода Веланда появился второй гитарист — Свен Терье Сольванг, затем группу покинул Хьетил Ингебретсен.
Пятый альбом группы, и второй на лейбле Stemhammer, вышел в 2007 году. 27 февраля 2007 года, вскоре после выхода альбома Illumination, стало известно, что из Tristania ушла бессменная вокалистка Вибеке Стене. После полугода поисков новой вокалисткой стала итальянка Марианджела Демуртас.
В январе 2010 года Tristania вошли в студию, чтобы начать запись нового альбома. Выход нового альбома, который получил название Rubicon, состоялся в августе 2010 года на австрийском лейбле Napalm Records.
31 мая 2013 года на лейбле Napalm Records вышел седьмой студийный альбом группы под названием Darkest White.
