Вдохновленные творчеством Tiamat и Paradise Lost, парни начали писать собственные композиции, однако из-за разницы во взглядах в 1997 году их творческий тандем распался. Пару лет у Марко ушло на отработку четкого видения проекта, и лишь затем гитарист озаботился подбором партнеров. В 1999 году Хойбаум пригласил к себе Роланда Крюгера и других членов только что распавшейся металлической команды и представил им ряд своих песен. Отобрав из этого материала пять композиций, музыканты записали их в маленькой студии и выложили в Интернет. Неожиданно для Марко и компании песни оказались очень востребованы, и это послужило толчком для превращения Xandria из простого проекта в настоящую команду.

После пары рокировок в составе, конфигурация группы приобрела следующий вид: Марко (гитара), Лиза Шапхаус (клавишные), Роланд (бас), Герит Ламм (ударные) и Энди (гитара). Первоначально ведущие вокальные партии исполнял Хойбаум, однако со временем оказалось, что голос Лизы звучит гораздо приятнее, и поэтому впоследствии именно она завладела микрофоном всерьез и надолго.

В 2001 году команда была уже достаточно популярна в андеграунде, и ей начали поступать заявки на концерты. Вскоре у группы появился менеджер, Удо Циммер, а деятельностью Xandria стали интересоваться лейблы. В этот период Энди уже не мог уделять команде достаточного внимания, и его пришлось заменить Филипом Рестемейером. В 2002-м помимо живых выступлений коллектив активно занимался подготовкой демок и благодаря этому получил контракт от Drakkar Records. В конце года под предводительством продюсера Дирка Райгнера закипела работа над первым альбомом, и в мае "Kill The Sun" уже лежал на прилавках. Дебют оказался весьма неплохим, и диск попал в национальный Топ 100.

По весне Xandria отыграли несколько концертов на разогреве у Subway to Sally, а затем отправились в большое турне в компании с Tanzwut. Потом были фестивали типа Mera Luna, гастроли с другой готической командой, ASP, а ближе к зиме музыканты занялись подготовкой второго альбома. На этот раз местом проведения сессий была избрана Бельгия, причем заправлял всем продюсер Хосе Альварес-Брилль.

В начале 2004-го команду покинул Крюгер, а новым бас-гитаристом стал Нильс Миддельхауфе. Законченный с его помощью альбом "Ravenheart" оказался для группы настоящим прорывом. Диск занял 36-е место в национальных чартах, где продержался в общей сложности семь недель. Популярность Xandria перешагнула границы Германии и добралась аж до Восточной Азии, куда музыканты были приглашены на самый большой оупэн-эйр Busan International Rock Festival. На этом фестивале группа играла перед 30-тысячной аудиторией, поэтому неудивительно, что следующие гастроли Xandria провели в качестве хедлайнеров.

Первую половину 2005 года коллектив потратил на работу над своим третьим альбомом. На этот раз в записи участвовало много приглашенных музыкантов, например участники австралийской команды Lyriel, ирландские фолкеры из Sceal Eile и даже Немецкий Кинематографический Оркестр. Несмотря на несколько необычный статус сессионщиков, альбом India получился потяжелее двух предыдущих работ. Интересный факт: незадолго до "индийского" релиза Нильс и Лиза узаконили свои отношения, став мужем и женой.

30 апреля 2008 Лиза Миддельхауфе покинула коллектив, ссылаясь на личные причины и дискомфорт в роли лидера группы. В феврале 2009 года было объявлено, что Керстин Бишоф (ex-Laconia) стала новой вокалисткой Xandria. В составе с новой вокалисткой группа возобновляет концертную деятельность, выступая не только в родной Германии, но и за ее пределами. Так, в 2009 г. Xandria впервые выступили в Чешской Республике и странах Южной Америки, а также на фестивалях Sazavafest Festival и Metal Mania Festival в Чехии, Birmingham Metal Fest в Англии.

Однако, пробыв в группе год, Керстин решила покинуть коллектив, из-за занятости и по личным причинам она пожелала сосредоточиться на своей немузыкальной карьере в будущем. Таким образом, выход нового альбома был вновь отложен на неопределенное время.

Не желая отменять из-за ухода Керстин уже запланированные выступления, Xandria привлекают в качестве приглашенной вокалистки Лизу Миддельхауфе и дают в оригинальном составе еще 3 концерта: два в Греции и один в России. Российское выступление, ставшее прощальным концертом Xandria в классическом составе с Лизой, состоялось 28 мая 2010 г. в московском клубе "ХО". Несмотря на многочисленные слухи, после совместных концертов Лиза не вернулась обратно в Xandria, и группа продолжила поиски новой вокалистки. Скопировано с Dark-World.ru.

7 декабря 2010 года группа опубликовала следующее сообщение:

20 декабря группа представила новую вокалистку. Ей стала Мануэла Краллер (Manuela Kraller), ранее работавшая с группой Haggard в качестве концертной вокалистки. Первое выступление в составе с Мануэлой состоялось 7 января 2011 года в родном для группы городе Bielefeld (Германия), в концертном зале Seidensticker Halle. Шоу Xandria проходило в рамках фестиваля Classic meets Pop, на котором группа впервые выступила с филармоническим оркестром и представила метал-жанр! В ближайшее время группа планирует приступить к записи долгожданного нового альбома, демо-записи инструментальных партий для которого уже полностью готовы, и отправиться в турне в его поддержку.

Лиза (Lisa Middelhauve) приняла участие в качестве приглашенной вокалистки в европейском туре австрийской группы Serenity в поддержку их нового альбома "Legacy & Death".