Excalion a été créé en Décembre 2000 à Konnevesi en Finlande. Le claviériste Jarmo ”Jappe” Myllyvirta a écrit quelques pièces power metal mélodique et il a commencé à chercher des membres pour former un groupe. La formation était composée de quatre personnes; Jappe, le batteur Henri Pirkkalainen, le bassiste Timo Sahlberg et le guitariste Tero Vaaja. C'est de cette manière qu'à été créé Excalion. La prochaine étape était de trouver un chanteur, Jarmo Pääkkönen s'est joint à eux, puisque son ancien groupe s'est séparé. Leur premier spectacle a eu lieu lors de l'été 2001 à Työväentalo, à Konnevesi. En plus de leurs pièces, ils ont fait des reprises de Stratovarius et quelques reprises de Nightwish sans vocal. Excalion a été complété lorsque le guitariste Kimmo Hänninen a joint le groupe. À l'automne 2001, ils ont enregistré leur premier démo, "Forlom". Il a été réalisé au Studio Kaktus, près de Jyväskylä, où ils ont eu deux jours pour enregistrer et mixer trois chansons. Le service militaire de quelques membres et d'autres difficultés techniques ont empêchés le groupe de faire des spectacles sur une base régulière.



En 2002 et en 2003, ils ont pu faire des concerts plus régulièrement. Jappe a également écrit de nouvelles pièces avec plus de détails et de variétés que les précédentes. À l'automne, Excalion ont débuté l'enregistrement de leur deuxième démo avec leur propre équipement et leur propre studio. Ils ont travaillé sur le démo par moment jusqu'à l'été. Le disque "Obsession To Prosper" a été créé.



À la fin de 2003, ils ont signé un contrat avec la compagnie Sound Riot Records et ils ont commencé l'enregistrement de leur premier album lors de l'automne 2004. Le disque inclut de nouveaux morceaux, en plus de quelques anciennes pièces retravaillées. Le tout a été réalisé au Studio Watercastle à Jyväskylä en Septembre. Le premier opus d'Excalion, "Primal Exhale", est mis en vente au mois de Février 2005. L'album est décrit comme étant un mélange de Stratovarius et de Nightwish. "Primal Exhale" a été enregistré et mixé au Watercastle Studios à Jyväskylä, en Finlande (Requiem), et masterisé à The Digital Audio au Royaume-Uni (Royal Hunt, Ring Of Fire et Last Tribe). La pochette a été réalisée par C.A. Interactive (Morifade, Axenstar, Supreme Majesty).