Следующие несколько месяцев оставшиеся музыканты Стив и Дейв пребывали в черной меланхолии, однако спустя какое-то время сумели справиться с депрессией и в 1978-м году нашли новых участников – ими стали бывший барабанщик Smiler по имени Doug Sampson и вокалист Paul Di’Anno. Пол (1959-го года рождения) прежде никогда не пел ни в одной известной группе. «Я сначала тренировался перед зеркалом с теннисной ракеткой в руке. А в 1978-м решил стать участником группы и выйти на настоящую сцену», – рассказал певец о начале своей карьеры.
Начинающий музыкант Пол ДиАнно с успехом прошел предварительное прослушивание и тут же был принят в Айрон Мэйден. С его появлением группа снова вернулась к жизни, радуя своих поклонников новыми композициями в исполнении Пола. Его необычный хрипловатый голос, обнаженный рельефный торс и короткие взъерошенные волосы являли собой образ рабочего парня – в конце концов, это стало визитной карточкой группы. Кроме того он являлся автором песен, которые сам исполнял. «Running Free» (самый первый хит группы), а так же знаменитый «Remember Tomorrow» – его творения.
После недавнего периода простоя дела музыкантов значительно улучшились, их творческая деятельность стремительно набирала обороты. К концу года ребятам удалось записать свою первую демо-ленту – запись проходила в студии звукозаписи Spacewood в Кембридже. Были записаны четыре вещи – «Prowler», «Invasion», «Strange Word» и «Iron Maiden». Все это обошлось музыкантам примерно в 200 фунтов стерлингов, хотя молодые люди намеренно выбрали для записи канун Нового года, чтобы получить скидку. Тем не менее, этих денег оказалось недостаточно для того, чтобы выкупить пленку, а когда группа вернулась через неделю, выяснилось, что студия уже стерла все сделанные ранее записи. Артистам ничего не оставалось, как воспользоваться кассетными записями. Демо особой популярностью не пользовалась до тех пор, пока музыканты не продемонстрировали ее лондонскому ди-джею клуба Bandwagon по имени Нил Кей. Основная его деятельность заключалась в организации концертов тяжелых рок-групп и проведении экстремальных дискотек в Soundhous (клубе, расположенном по соседству). Нил был очень известной личностью в своем кругу, его мероприятия пользовались большим успехом, поэтому он не воспылал желанием тратить свое время на прослушивание каких-то записей от малоизвестных «Мэйден». Только спустя три недели он все же сподобился вставить пленку в кассетник и, то, что он услышал, его потрясло.
«Это было как озарение» – рассказал позже Нил в своем интервью – я носился кругами по квартире, слушая запись снова и снова. Потом я позвонил Стиву и сказал, что эта кассета – настоящая сенсация, на что он просто рассмеялся. Он подумал, что я шучу».
Нил опробовал демо на одной из своих дискотек и публика была в восторге. Айрон Мэйден стали частыми гостями в клубе Bandwagon, а число их поклонников стало стремительно увеличиваться. Затем на одну из кассет наткнулся некий Род Смоллвуд, и он предложил музыкантам стать их менеджером.
С этих пор группа стала гастролировать по стране, давая концерты во всех уголках Англии. Вскоре стали появляться компании, предлагающие «Мэйден» заключить контракт на запись диска с одним условием – группа должна играть панк, но музыканты менять свой стиль не захотели.
К концу 1979-го года ситуация в мире музыки несколько изменилась – панк стал постепенно выходить из моды, уступая место новым, более тяжеловесным музыкальным направлениям. Айрон Мэйден становятся все более популярными, растет число поклонников. Журналист Джефф Бартон опубликовал в «Sounds» большую статью о модном музыкальном направлении хэви-метал, в которой говорилось и об Айрон Мэйден, как о представителе данного стиля.
Из-за постоянной концертной занятости музыканты были вынуждены оставить все свои прежние работы и полностью погрузиться в мир музыки. Популярность «Железной Девы» продолжала расти. 3 сентября артисты участвовали в подпольном концерте Motorhead, проходящем в клубе «Music Machine». А 6 сентября с группой произошло забавное происшествие – непосредственно перед выходом на сцену Пол ДиАнно был арестован полицией за ношение холодного оружия. В итоге Айрон Мэйден пришлось выступить в неполном составе, играя музыку без текста. Хотя некоторые песни все же были исполнены – Стив Харрис выступил в роли вокалиста.
13 октября «Мэйден» стали одними из участников концерта, состоявшегося на престижной лондонской сцене «Marquee». Все билеты были распроданы задолго до начала представления (зал «Marquee» был рассчитан на 700 человек). Среди публики оказался и Джон Дарнли – представитель крупнейшей корпорации грампластинок EMI. Он был настолько впечатлен талантливой игрой музыкантов, что сразу же предложил ребятам заключить контракт на несколько альбомов.
Тем не менее, через четыре дня свой первый сингл под названием «The Soundhouse Tapes» группа выпустила под собственным лейблом Rock Hard Records (в честь клуба Нила Кея). В него вошли те три вещи с демо-ленты, которые мы уже знаем – «Iron Maiden», «Prowler» и «Invasion». Всего было выпущено 5000 экземпляров, которые сразу же раскупили, и это несмотря на то, что приобрести пластинку было не так просто – ее можно было заказать по почте, либо купить на концерте группы.
А между тем Iron Maiden требовался еще один гитарист. В начале 1979-го года предложил свою кандидатуру некий Paul Cairns, но спустя два месяца он покинул группу. Затем нашелся еще один музыкант по имени Paul Todd, который в силу личных обстоятельств не мог полноценно отдаваться работе и ездить на гастроли – он продержался в группе не более двух дней.
К концу года «Мэйден» все же удалось найти гитариста, с которым они, наконец, сработались. Его имя было Tony Parsons, и именно с ним группа записала композиции «Sanctuary» и «Wrathchild» для EMI. Они были выпущены в начале следующего года в сборнике «Metal For Muthas», в который помимо песен Iron Maiden вошли синглы групп Saxon, Angelwitch и Praying Mantis.
Однако Тони Парсонс не воспылал желанием продолжать сотрудничество с «Железной Девой». На сцене он чувствовал себя не в своей тарелке, играл без удовольствия и, в конце концов, ушел из коллектива, а за ним последовал и барабанщик Дуг Сэмпсон, который не смог продолжать концертную деятельность по состоянию здоровья. А на смену им в группу пришли новые музыканты – гитарист Dennis Stratton и барабанщик Clive Burr. Деннис – фигура никому не известная, чего нельзя сказать о барабанщике. В недавнем прошлом Клайв Барр записался в «Mr. Rock N Roll» группы Samson – самом раннем сингле «новой волны британского Heavy metal».
В новом составе Айрон Мэйден вместе со своим продюсером Will Mallone поехали в звукозаписывающую студию создавать свой дебютный альбом. А до его выпуска вышел сингл с двумя композициями на каждой стороне – «Running Free» и «Burning Ambition». Последняя вещь была записана еще в прежнем составе группы. Что же касается «Running Free» – это один из самых ярких хитов за всю творческую жизнь «Железной Леди», поэтому нет ничего удивительного в том, что сингл сразу же оказался в Тор-50 английского хит-парада.