Le groupe heavy/power metal anglais a été créé au début 2004 par Christopher Bowes, Gavin Harper et Graham Motion (R.I.P). Stuart Finny de Splen a été recruté dans le groupe comme bassiste avec Tom Mitchell de Allergo Fame à la guitare. Battleheart mentionne qu'il joue du Heavy Metal Pirates, parmis les premiers groupes à avoir fait cette mention est Running Wild. Le groupe pratiquait une reprise de "Holy Thunderforce" de Rhapsody. Il y a eu plusieurs changements dans l'alignement, incluant quelques participations au vocal de Robin Hell et Brendon Mcsteel (guitare) a joué avec eux seulement une journée. Leur premier enregistrement officiel a été réalisé à la fin 2004 avec Rawb de Aces High (Then Rock Fist) au vocal. Après avoir décidé de se concentrer sur Rock Fist, Rawb a quitté et Gabriel de Deceiver s'est joint à eux pour un second enregistrement de "Over The Seas". Ce dernier quitte également pour son autre projet, mais la distance n'était en rien.




Deux tentatives d'enregistrement d'une démo ont échoué à la maison de Gavin, avec trois disques durs brisés et le batteur s'est cassé un bras. À l'été 2005, le groupe s'est reformé avec Christopher (claviers), Gavin (guitare), Robin Hell (vocal), et une machine pour la batterie. Cependant, Gavin se construisait un studio maison, ce qui a permis à Battleheart d'enregistrer leur EP en avril 2006. Les réponses étaient excellentes, et le groupe a pu débuter les spectacles et ajouté dans ses rangs le guitariste James Foote, Dani Evans à la basse et Douggernaught à la batterie. James a quitté en raison de l'école et de son engagement avec Questioned by Theory. Toujours en 2006, Battleheart enregistre le EP "Terror on the High Seas" avec Dani à la basse, Doug à la batterie, Christopher au vocal/clavier et Gavin aux guitares.