Die Metal Band wurde im Jahre 1999 von Jyri Vahvasen, der bereits als Moredhel Mitgründer bei der Band Horna gewesen war , und Miika Kokkolan gegründet. Die noch im selben Jahr veröffentlichte Promo-CD Warrior's Tale fand bei den Plattenfirmen keinen großen Anklang und wurde auch von Jyri Vahvasen selbst als „schlecht“ bezeichnet. Mit Dark Fantasy wagten Battlelore 2000 einen neuen Versuch. Hierfür wurde die Studentin Kaisa Jouhki gebeten, hohen Klargesang einzusingen, als Gegenpart zum tiefen, rauen Männergesang. Fortan stieg sie allerdings sofort als festes Mitglied bei Battlelore ein. Für die Plattenfirma Napalm Records wurden drei weitere Lieder eingespielt und die Gruppe anschließend unter Vertrag genommen.

Im Herbst 2001 wurde das erste Album ...Where the Shadows Lie in den Music-Bros. Studios, in denen schon die Promos entstanden, aufgenommen. Gitarrist Tommi Havo verließ die Band daraufhin aus persönlichen Gründen und wurde nach einer Weile durch Jussi Rautio ersetzt.

Das zweite Album Sword's Song erschien im Frühjahr 2003. Mit diesem Material im Gepäck tourte Battlelore im Rahmen der The Magic of Angels Festival Tour 2003 erstmals durch Deutschland, Spanien, Belgien, Niederlande, Österreich und die Schweiz.

Anfang 2004 folgte dann die DVD The Journey. Sie enthielt ein rund halbstündiges Konzert, das im finnischen Tavastia-Club aufgenommen wurde, Musikvideos sowie Gespräche mit den Bandmitgliedern. Hierauf verließ Sänger Patrik Mennander die Band, um sich stärker seiner Arbeit als Frontmann der Gruppe Ruoska zu widmen. Sein letzter Auftritt mit der Band fand auf der Ring*Con in Bonn statt.

Mit Unterstützung durch den Gastsänger Tomi Mykkänen und den Gastbassisten Timo Honkanen absolvierten Battlelore ihre Europa-Tour Atlantis Lovelorn. Aus persönlichen Gründen verließ dann 2005 mit Miika Kokkolan wiederum ein Mitglied die Band. Auf der Suche nach einem neuen Sänger und einem neuen Bassisten wurde kurzerhand bei den beiden Gastmusikern angefragt und beide gehören seitdem zur festen Besetzung der Band. Im gleichen Jahr veröffentlichten Battlelore ihr drittes Studioalbum Third Age of the Sun.

Im Februar 2007 erschien das vierte Album Evernight. Diese Platte wurde vom Gitarristen und Texter Jyri Vahvasen in Nachhinein als „kryptisches Album“ bezeichnet, da darauf kein direkter Bezug auf Tolkiens Welt genommen wird, und die Texte somit universell interpretierbar sind.

Am 26. September 2008 wurde das fünfte Studioalbum mit dem Titel The Last Alliance veröffentlicht. Im Gegensatz zum Vorgängeralbum bezieht sich diese Scheibe wieder verstärkt direkt auf Tolkiens Werke. Der Titel The Last Alliance bezieht sich laut Vahvasen zum einen auf das letzte Bündnis aus Menschen und Elben, das im Dritten Zeitalter gemeinsam gegen den Dunklen Herrscher Sauron zu Felde zieht (erwähnt in „Herr der Ringe“), zum anderen jedoch auch darauf, dass Battlelore mit diesem fünften Album ihren Plattenvertrag bei Napalm Records erfüllt haben und somit eine Ära endet. Ob ein Wechsel zu einem anderen Plattenlabel erfolgt, lies Vahvasen offen. ^[3] Auf der Titelseite des Albums ist Sauron abgebildet, mit dem Ring der Macht am Finger, geschaffen vom deutschen Illustrator Ingo Römling. The Last Alliance erschien auch als limitierte Fassung, die eine DVD beinhaltet, die einen Live-Auftritt der Gruppe beim „Metal Female Voices Festival 2007“ zeigt.