V roce 1996 dva bývalí členové Uzi Suicide, Morten Veland a Einar Moen spolu s Kennethem Olssonem založili kapelu Tristania. Krátce před natočením dema v roce 1997 se skupina rozrostla o další členy: Vibeke Stene, Anderse Hidle a Rune Osterhuse. O rok později vydali své první album, Widow's Weeds.

V roce 1999 vydali své legendární album Beyond the Veil. Po práci na Beyond the Veil, pro vnitřní neshody odešel leader kapely Morten Veland.

V roce Tristania 2001 vydali své třetí album, World of Glass, na kterém se do jejich tvorby přidalo více chórů, „nadupanosti“ a elektronické prvky. Na tomto albu se se spoluprací podílelo mnoho interpretů, jako jsou Anathema, Tiamat, The Sins of Thy Beloved, Trail of Tears, Haggard, Solefald, Darkwell, Cradle of Filth, Theatre of Tragedy, Elusive, Lacrimosa, Blindfolded, Zeromancer a další. Ke kapele se také připojili další členové, Isten Bergly a Kjetil Ingebrethsen.

Jejich další album, Ashes, vydané v roce 2005, se nese v duchu zjednodušení. Pryč jsou velkolepé chóry, zpěv je jakoby zjednodušen a atmosféra je lehčí. Přesto album sklidilo nemalé úspěchy a posunulo styl Tristanie zase trošku jinam, což se konec konců u Tristanie děje pořád –album od alba je jednoduše rozpoznatelné.