Уже к середине 90-х появились предпосылки для образования группы Xandria в нынешнем её виде. Вдохновленные такими командами как Тiamat
и Paradise Lost, Марко Хеубаум и его друзья осмелились совершить свои первые шаги в области потрясающего звучания хард-рока и гитарных риффов. Но в следствие различных взглядов на музыкальные ориентиры, группа (включая вокалистку и Марко в качестве певца и гитариста) раскололась в 1997. В результате музыкальное видение Марко стало более чётким,после чего он снова занялся поиском музыкантов.

1999 год - репетиции группы. Марко представляет свои первые песни для проекта Xandria с обновлённым составом, включающим Роланда Крюгера (Roland Krueger) с его коллегами из только что распавшейся группы Bielefeld. Среди песен такие как "Kill the Sun", "Casablanca" и "So You Disappear", оригинальные версии которых были созданы ранее в 1994 году как первые шаги музыкальной карьеры.

В 2000 году проект стал реальной группой. В маленькой студии были записаны 5 песен, представленные на обозрение публике в конце года на интернет сайтах типа "mp3.de" или "besonic.com". Демо версии песен неожиданно стали хитами в андеграундных кругах. Огромная фанатская аудитория расширялась довольно быстро и в других странах, к примеру в США, опять же через интернет-сайт "mp3.com". Всё это не могло пройти бесследно и Марко решил сделать проект реальной группой. После 2-х изменений в составе, Xandria к тому моменту состояла из Марко, Лизы, Джерита, Роланда и Энди (предшественника Филипа, присоединившегося уже в следующем году). В дополнении можно сказать,что первые демо-песни наполовину состояли из вокала самого Марко, т.к. идея использования женского вокала была применена только в некоторых частях, но в дальнейшем стала практиковаться всё чаще. Только "Kill the sun" была представлена женским вокалом, навеенная "Lady Rosenred", песней шведской группы Lake of Tears. Но сейчас Марко отдаёт предпочтение песням, исполненным именно Лизой.

В 2001 году группа становилась всё более известной в андеграунде и даже получала приглашения на небольшие концерты. Группа вступает в связи с музыкальным бизнесом, среди других и с Udo Zimmer, затем ставшим их менеджером . Для группы открылся путь на несколько лэйблов, намерения которых были более чем серьёзными. Музыкальные занятия недалеко от Oldenburg заставили второго гитариста Энди покинуть группу. На его место после долгих поисков пришёл Филип, родом из городка Bielefeld. Выясняется,что он и Лиза уже знакомы.

2002 год примечателен живыми выступлениями на андеграундном уровне и тяжёлой работой над новым демо, так как Drakkar проявил интерес и хотел услышать большеe от группы, чей профессиональный рост был очевиден по отношению к демо 2000. Наконец, Drakkar Records и группа подписывают соглашение о записи в декабре - пока группа уже работает на первым полноформатником с продюссером Dirk Riegner.

В 2003-м году альбом "Kill the sun" поступает в продажу и даже попадает в немецкий чарт альбомов - замечательный успех для дебюта. Уже после того, как группа отыграла несколько шоу с Subway to Sally весною, начался первый большой тур вместе с Tanzwut. В течение этих трёх недель вокруг Германии группа завоёвывает новых поклонников и активно общается с ними. После таких фестивалей, как "Mera Luna", и другого тура с готик- группой ASP, Xandria в течение зимы вновь отправляются в студию. Этот год,столь наполненный событиями,принёс с собой множество новых идей, не желая медлить со вторым альбомом, группа приступает к работе.

2004-й год начался с плохой новости для Xandria - басс-гитарист Роланд оставляет группу по профессиональным причинам. Поиски замены, сопряжённые с множеством прослушиваний, наконец-таки завершились успехом. Новым басс-гитаристом стал Nils Middelhauve. Он не был известен членам группы, кроме Лизы, которая несколько лет назад поддерживала его прежнюю группу - Visible Touch как сольный исполнитель. Они также были известны Марко, который единожды написал в местные фан-зины.

Второй альбом "Ravenheart" появился на прилавках магазинов 24-го мая и оказался на удивление успешным. Альбом продержался в течение 7 недель в top-40 немецких альбомов. Был снят первый видеоклип Xandria на песню "Ravenheart", который пользовался высокой популярностью у зрителей. Клип представляет собой короткий фантастический фильм с множеством атмосферных изображений и выделяется из многочисленных стандартизированных клипов. Тем временем Xandria принимает участие в самом большом открытом фестивале Юго-Западной Азии: выступление на "Busan International Rock Festival"обернулось реальным шоу с 30 тысячами восторженных зрителей.

После выступления на "Summer Breeze Festival", вблизи Берлина, в старом замке был снят видеоклип к балладе "Eversleeping". 11 октября был выпущен сингл с одноименным названием, на который вошли три новых песни (среди которых и ремейк на очень старую песню группы 1997 года - "So Sweet"). Сингл продержался в чартах в течение двух недель.

В ноябре 2004 группа начинает свой столь продолжительный тур в качестве хэдлайнеров, совместно с финской группой Entwine и LAB на разогреве, который принёс адское удовольствие поклонникам и утвердил Xandria как группу, дающую отличные "живые" шоу. Более роковое звучание песен,чем представленное на альбоме, было с воодушевлением воспринято поклоннниками. А вновь собранные впечатления и энергия стали поводом к написанию новых песен. И группа садится в студию в декабре для записи преемника "Ravenheart".

Первая половина 2005 года прошла без перерыва в работе над новым альбомом. Появилось множество идей, нашедших выражение на альбоме "India", выпущенном 22 августа 2005 года. Среди них: сотрудничество со знаменитым немецким оркестром "Deutsches Filmorchester Babelsberg", работающим над саундтрэками к фильмам, и с немецкой фолк-группой Lyriel. После месяцев напряжённой работы альбом был закончен. Результат стоил всех приложенных усилий - на данный момент это самая зрелая работа группы. И ещё одно важное событие произошло в жизни группы в 2005 году.. Нильс и Лиза поженились после года серьёзных отношений.

2006-й год выдался удачным временем для концертной деятельности. Группа даёт множество выступлений в поддержку альбома "India". Так же Xandria принимают участие в "Romantic Darkness Tour" с Regicide, Visions of Atlantis, Lyriel и Admirabilis и множестве фестивалей (Wave Gotik Treffen, Сastle Rock, Metal Female Voices Festival, Rock the Bock Festival и др.)
30 марта 2006 года начинает работу русский сайт о группе Xandria - NOW AND FOREVER, группа приобретает всё большую популярность в России. И, к радости русских поклонников, в рамках мини-тура по России 30 июня группа даёт концерт в Твери, 1 июля выступает в Москве в клубе "Апельсин" и кроме того 7 июля Xandria принимают участие в фестивале «Псковский Циклон».

2007-й год начался с работы над новым, 4-м по счёту альбомом Xandria. Работа получила интересное название "Salome - The Seventh Veil". За основу была взята библейская легенда о танце Саломеи, дочери Ирода, с семью покровами. Для записи на этот раз была выбрана Principal Studios в Германии, а продюсированием занялась непосредственно сама группа (благо для Марко это не впервые). На ОФИЦИАЛЬНОМ ФОРУМЕ группа оставляла записи для студийного дневника, так что поклонникам была предоставлена возможность узнать о том, как проходит запись. Так же Лиза в этот период записывает свои бэк-вокальные партии для нового альбома итальянской хэви-метал группы THE DOGMA.

25 мая 2007 года альбом поступил в продажу. Группа приготовила слушателям "более прямой, разноплановый и эксперементальный альбом, приближенный к реальности, но и не лишённый привычных для звучания группы элементов". Из особенностей можно отметить более "роковой" саунд, характерный для выступлений группы, эпичность заглавной песни "Salome" и дуэт с Миккой из ENTWINE в "Only For The Stars In Your Eyes". С 23 по 27 мая группа даёт несколько шоу в Германии в рамках Salome Mini-Tour с группой MONO INC. на разогреве. Так же в планах у Xandria выступления на летних фестивалях в Германии, 2 шоу с Tanzwut и несколько сольных, и съёмки видеоклипа на песню "Save My Life" .