В середине 80-х гитарист Бэрри "Бари-Бари" Гэлвин и басист Йохан Шуманн работали в культовой готик-роковой бригаде "Christian Death", причем первый из них также сочинял песни и в плане авторства пытался составить конкуренцию тогдашнему лидеру команды Валору Кэнду. Последний момент, видимо, и послужил причиной конфликта между музыкантами, и во избежание дальнейшего нарастания страстей Бэрри покинул состав. В ту пору творческих амбиций у Гэлвина вполне хватало, и он, прихватив с собой Шуманна, сразу же начал собирать собственную группу, а поскольку предшествующие события происходили в Дюссельдорфе, то в проект оказались подписаны и два германских музыканта, барабанщик Арнд Виллерт и вокалист Йорг Вестерманн. Скорее всего, по той же причине свежеиспеченная команда получила немецкоязычное имя "Mephisto Walz", однако эту идею подкинул Йохан, несколько переделавший название американского хоррор-фильма "The Mephisto Waltz". Практически с колес коллектив выпустил первый EP на итальянском лейбле "Supporti Fonografici", но потом начался период неразберихи и затишья.
Гэлвин вскоре вернулся в Лос-Анжелес, где начал работать над новым материалом, хотя при этом лишился всех прежних партнеров. Какое-то время ему помогали Дэйвид Хёрмон (бас), Мондо (вокал) и Нарики Симука (гитара), однако потом Бари-Бари решил, что в группе не хватает женского голоса, и вновь взялся кроить штатное расписание. В итоге в начале 90-х с Кристианной у микрофона (она же Кристин Элизабет Ленард) и Стевином Греем на ударных был записан еще один миньон, и вскоре песни с него вместе с композициями с первой пластинки вышли на сборнике "Crocosmia".
Полноценный же альбомный дебют "Mephisto Walz" состоялся в 1993-м, причем здесь саунд успел заметно мутировать в сторону электроники и представлял собой что-то типа приготиченного нью-эйджа или эмбиентного готик-рока. Тем не менее уже на следующей пластинке гитары вернулись на свое место, а композиции стали более структурированными. Кроме того, на "The Eternal Deep" существенно добавился темп, и местами даже присутствовала агрессия, и в том числе все это проявилось в каверах "Stooges" ("I Wanna Be Your Dog") и "Rolling Stones" ("Painted Black"). Впрочем, вскоре такому развороту нашлось вполне логичное объяснение, поскольку диск 1994 года по большому счету представлял собой сборник раннего материала, причем часть вещей для него была перезаписана, а другая осталась в оригинальном виде. В середине 90-х Шуманн вернулся на свое место, а за ударными очутился Дэйвид Гласс, и в их компании Бари-Бари и Кристианне удалось найти компромиссный вариант между звучанием "Terra Regina" и "The Eternal Deep".
Как и два предыдущих диска, "Thalia" распространялся по каналам "Cleopatra Records", но вот релиз 1998 года завершил сотрудничество с этим лейблом. К тому моменту состав группы сократился до дуэта, а изданный усеченной версией альбом "Immersion" получился наиболее гомогенным и по мнению некоторых обозревателей характеризовался как мрачный ньювэйв. Далее наступила продолжительная пауза, однако на рубеже веков "Mephisto Walz" напомнили о себе ретро-сборником "Early Recordings".
Наконец в 2004-м вышел альбом "Insidious", в отличие от предшественника пестривший разнообразием и представлявший слушателю как довольно жесткие номера и вещи в духе "Siouxsie & The Banshees", так и полуэмбиентные треки и даже нечто похожее на оперу. В дальнейшем Бари-Бари стал уделять повышенное внимание проекту "Scarlet's Remains", а деятельность его команды была приостановлена, но с наступлением десятых "Mephisto Walz" вернулись на сцену. Камбэк-альбом не зря назывался "IIIrd Incarnation", поскольку во-первых, здесь Гэлвин попробовал петь сам, а во-вторых, его основной партнершей по микрофону стала Сэра Рид. Более того, изменилась и музыкальная формула, и песни группы стали жестче и напористее, а в таких вещах как "Keep Me From Walking" звучал почти что панк-рок. Продолжая искать новые формы звука, на следующем альбоме "Mephisto Walz" добавили атмосферности, а заодно вместе с оригиналами воткнули в трек-лист целых три кавера, "Poupee De Cire, Poupee De Son" от Сержа Генсбура, "Walking In The Air" от Хаварда Блэйка и легендарный "Kashmir" от "Led Zeppelin".
Кстати, на "New Apostles" голос Сэры можно было услышать только в последней композиции, а за остальные партии женского вокала теперь отвечала Мириэм Гэлвин. Впрочем, со временем Бэрри похоже вошел во вкус по части пения, и поэтому на альбоме "Scoundrel" подавляющее большинство вокальных партий исполнил сам. В 2018-м вышла перемикшированная версия "Immersion", а спустя пару лет "Mephisto Walz" выпустили полнометражку "All These Winding Roads", на которой были представлены как свежие треки, так и архивные вещи, причем Бари-Бари собрал целую команду вокалисток, а среди новых лиц появилась Кристианна.