Over the Hills and Far Away стал первым мини-альбомом (EP) группы. Он вышел в мае 2001 года, и финская, вышедшая на Spinefarm, версия включает: кавер на классическую композицию Гарри Мура "Over The Hills And Far Away", две оригинальные новые песни "Away" и "Tenth Man Down", а так же перезаписанную композицию "Astral Romance". Впервые эта песня появилась на первом альбоме группы, но в этой версии партию Туомаса исполнил замечательный вокалист группы Sonata Arctica Тони Какко, хороший друг Туомаса. Более того, Туомас и Тони подпели Тарье в конце песни "Over The Hills And Far Away". В "Tenth Man Down" появился еще один приглашенный музыкант - ранее участвовавший в записи "Oceanborn" Тапио Вильска.
Кроме того, существуют другие версии этого ЕР. Европейское издание Spinefarm включает, помимо этих четырех трэков, живые записи с концерта 29 декабря 2000 в Тампере песен "The Kinslayer", "She is My Sin", "Sacrament of Wilderness", "Walking in the Air", "Beauty and the Beast" и "Wishmaster". Издание Drakkar аналогично, только еще добавлен живой трэк "Deep Silent Complete". А в 2007 году появилось издание под названием Spinefarm UK Reloaded edition. Туда вошли все перечисленные трэки, а еще живые версии "10th Man Down", "Over the Hills and Far Away" и видео на одноименный трэк.
Интересно, что песня "Tenth Man Down" широко использовалась французским каналом TPS в качестве закадровой музыки, правда, нигде не было указано, что это именно Nightwish, так что никакой дополнительной рекламы группа себе на этом не заработала.
Так же, в 2001 году Pasi Takula снял для Nightwish видеоклип на заглавную композицию мини-альбома. Впервые в кадре появилась вся группа, а не только Тарья, которая исполнила главную роль в истории про заключенного. Кроме того, в роли темного волшебника в клипе снялся менеджер группы, Эво Похъола. Видео получилось очень атмосферным, одновременно интересным и забавным.
