Трудно запихнуть Battlelore в определённые рамки, в музыке соединились слишком многие вещи. True arctic fantasy metal - вот термин, который предпочитают использовать сами музыканты. Дебютный альбом Where the Shadows Lie был записан в Music Bros. Studios осенью 2001 года. Обложку делал Тед Насмит, очень уважаемый канадский художник, который сделал много работ по толкиеновской теме. Название этой картины - 'Моргот и Король Нолдор', здесь запечатлён момент схватки, к которой погибает Фингольфин, король эльфов Нолдор… Как вам уже, наверное, понятно, лирика альбома инспирирована произведениями Толкиена о Средиземье. Их продюсер Миитри Аалтонене и студия Music Bros. практически неизвестны в металлическом мире. "Он не работал с металлическими группами, поэтому ты о нём и не слышал, но это одна из главных причин работать с ним. У него много свежих и неожиданных идей, и он не боится экспериментов" - говорит вокалистка группы. Кроме того, Миитри ещё и подпевал на альбоме. А среди приглашённых музыкантов есть даже классический гитарист. Запись была закончена в ноябре 2001 года и издана 11 февраля 2002 года.