Предтечею цієї групи стали перші експерименти з музикуванням Марко Хойбаума і його друга, вжиті ними в середині 90-х. Натхненні творчістю "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 "вийшов поважче двох попередніх робіт. Цікавий факт - незадовго до "індійського" релізу Нільс і Ліза узаконили свої відносини, ставши чоловіком і дружиною.