Для привлечения большего внимания Смоллвуд посоветовал издать три песни — «Invasion», «Iron Maiden» и «Prowler» — отдельным синглом, который можно было бы распространять на концертах. Предложение было осуществлено с выходом сингла «The Soundhouse Tapes» (в честь заведения Нила Кея), выпущенном на собственном лейбле группы Rock Hard Records. Было напечатано 5000 копий, которые разошлись в считанные месяцы, даже учитывая тот факт, что купить пластинку можно было только на концертах группы или заказав по почте.

Группа также получила внимание со стороны прессы: ведущий рок-журналист Джефф Бартон впервые посвятил им отдельную статью в журнале Sounds, где помимо прочего печатал серию статей о группах-представительницах Новой волны британского хеви-метала.

Рост популярности привлёк внимание представителей компании EMI, которые, впечатлённые концертом группы, незамедлительно подписали с ними контракт (декабрь 1979 г.).

Напряжённая работа, плотный гастрольный график, алкоголь, курение, недосыпание — всё сразу сказалось на здоровье Дага Семпсона, послужив причиной его ухода. Новым ударником стал Клайв Барр (Clive Burr) (ум. 2013 г.) из группы Samson, которого пригласил на прослушивание только что присоединившийся к группе гитарист Дэннис Стреттон. Новый состав сразу же отправился в студию записывать дебютный альбом с продюсером Уилом Меллоном (Will Mallone). Однако ещё до его выхода на прилавках магазинов появляется сингл с песней «Running Free» (на второй стороне была помещена вещь «Burning Ambition», записанная ещё в старом составе). Несмотря на свою простоту, «Running Free» — одна из самых ярких песен в творчестве Iron Maiden раннего периода, и неудивительно, что сингл без труда попал в Top-50 английского хит-парада. На обложке этого сингла впервые появляется Эдди. В марте 1980 года впервые после The Who Iron Maiden выступили живьём в программе Top Of The Pops. Выступление в передаче способствовало росту успеха группы, в итоге сингл «Running free» поднялся до 34 позиции в английском хит-параде.

Дебютный альбом, одноимённый группе — Iron Maiden — вышел в апреле 1980 года и сразу имел успех: он поднялся до четвёртого места в британском чарте продаж альбомов, что и неудивительно, так как альбом представлял собой собрание лучших песен, исполняемых группой на протяжении предыдущих четырёх лет. Альбом представлял собой хеви-метал в духе Black Sabbath, но более быстрый и энергичный, с некоторым влиянием панк-рока, с воинственными и разнузданными текстами. Уже на первом альбоме, оформителем которого выступил Дерек Ригз, начало появляться чучело чертёнка-зомби, прозванного Eddie the Head (Эдди-голова). Эдди стал талисманом группы и отныне изображался на всех обложках её альбомов. Эдди появлялся также на сцене во время концертов группы (сначала в маске выбегал Род Смоллвуд, затем — тур-менеджеры). На обложках двух ранних синглов, «Sanctuary» и «Women in Uniform», Эдди был изображён дерущимся с Маргарет Тетчер, премьер-министром Великобритании, что поначалу стяжало группе протестную и слегка скандальную репутацию.

В мае группа отправилась в большое английское турне, открывая выступления Judas Priest, а затем устроила серию собственных концертов. Перед выступлением в Эдинбурге выяснилось, что Клайв Барр заработал серьёзное расстройство желудка и не может играть. Тем не менее, глава гастрольной команды Вик Велла и другие дорожники принесли Клайва на сцену на руках и усадили за ударную установку. Концерт он отыграл, но по его окончании упал в обморок, не вставая из-за барабанов. В конце лета Iron Maiden поддерживают в Европе Kiss и играют на фестивале в Ридинге перед UFO. По возвращении с гастролей Деннис Стрэттон покинул группу из-за личных и творческих разногласий с Харрисом.