לאחר הקלטת דמואים שונים והצלחה מרובה בפורטלי MP3, הם שחררו את אלבומם הראשון ב-2003 הנקרא Kill The Sun ("הרוג את השמש"), שהגיע למקום ה-98 במצעדי המוזיקה הגרמנית. האלבום שהגיע מיד אחריו,ב-2004 ונקרא Ravenheart , נשאר במצעדים למשך כ-7 שבועות, והגיע למקום ה-36. ב-2005 הם שחררו את אלבומם השלישי, India ("הודו"), שמופנה יותר לסגנון הסימפוניק מטאל. ב-14 בדצמבר 2006 קסנדריה החלו בהקלטות ובהכנות לאלבומם החדש והרביעי שנקרא-Salomé - The Seventh Veil , ששוחרר ב-25 במאי 2007.