Tristania a été fondé en 1996, avec Elinor Moen (au synthétiseur et programmes), Kenneth Olsson (à la batterie) et l'ex-chanteur/guitariste Morten Veland.

C'est suite à la rupture d'avec le groupe Uzi Suicide que Moen et Veland ont créé Tristania. Ils réussissent à convaincre Olsson de faire partie de leur nouveau groupe. Rapidement, Sterhus (à la basse) et Anders H. Hidle (à la guitare) les rejoignent.

En mai 1997, le groupe enregistre sa première "démo" (qui s'appelle Tristania) en Klepp Lydstudio. En même temps, Vibeke Stene était présente comme musicienne de session, mais le restant du groupe était persuadé que sa voix collait parfaitement. Elle devient donc le sixième membre du groupe.

Avant fin 1997, l'album Widow's Weeds est enregistré et mis en vente en début 1998. Cet album peut-être qualifié de métal symphonique, avec différentes influences telles que la Scala gothique, le Death metal, la musique classique et le black metal.

Sten Bergnothingy, qui est aujourd'hui est un membre du groupe, participe avec un vocal masculin dans la chanson Angellore.

Après leur album "Beyond the Veil" en 19< src=om