Новым гитаристом стал Эдриан Смит, лидер группы Urchin и бывший одноклассник Дейва Мюррея. Его приглашали присоединиться к Iron Maiden ещё перед Дэннисом Стреттоном, но Эдриан надеялся достичь успеха со своей группой, но это ему всё же не удалось.

В декабре Iron Maiden в очередной раз выступили новаторами: компания EMI выпустила полную версию их концерта в the Rainbow Theatre, на что до этого момента никто не решался.

Второй альбом, Killers, был довольно холодно встречен критикой, хотя на этот раз продюсером выступил Мартин Бирч, который сделал звучание альбома намного лучше своего предшественника, Iron Maiden провели свой первый мировой тур, посетив США, Канаду и Японию. В это время большинство музыкантов были недовольны работой вокалиста ди Анно: он много выпивал, употреблял наркотики и часто не мог петь на необходимом уровне. Решением группы Пол был уволен, его место занял Брюс Дикинсон (ещё один бывший участник Samson), ставший позднее самым известным «голосом» Iron Maiden. Ди Анно продолжил карьеру, основав одноимённую его последнему альбому с «девой» группу Killers, однако известным по нынешнее время остаётся лишь как первый вокалист Iron Maiden.

Международная популярность. Эксперименты со звучанием (1981—1989)

Появление менее панкового и более артистичного, чем Ди Анно, фронтмена сопутствовало росту популярности группы. В 1982 году вышел The Number of the Beast (Число Зверя), третий альбом группы и первый с участием Дикинсона. Брюс, хотя исполнил все вокальные партии на альбоме, даже не значился в титрах при первом издании, так как имел контракт с другой компанией, угрожавшей ему иском. Альбом стал прорывом для группы, заняв первое место в чартах продаж в Британии, попав в десятку лучших в США, Канаде и Австралии. В поддержку альбома группа провела тур Beast on the Road, завершившийся аншлаговым концертом в нью-йоркском Палладиуме. Американская часть турне сопровождалась давлением со стороны общественности, поскольку группа была обвинена в сатанизме из-за титульного трека альбома.

В декабре 1982 года барабанщик Клайв Барр покинул группу из-за личных проблем и сложностей с дальнейшим пребыванием в группе. На замену ему был приглашён барабанщик Нико МакБрэйн, с участием которого группа в скором времени выпустила следующий альбом Piece of Mind. Новая пластинка стала первой, достигшей платинового статуса в США.

Вдохновлённые успехом пластинки, Iron Maiden в сентябре 1984 года выпустили альбом Powerslave, который включил полюбившиеся поклонникам песни «2 Minutes to Midnight», «Aces High», и «Rime of The Ancient Mariner»,. Тур World Slavery Tour, проведённый в поддержку альбома, до недавнего времени был самым масштабным в истории группы, поскольку включал 193 выступления и длился более 13 месяцев. Тур являлся одним из самых грандиозных в истории рока. Эдди теперь управлялся не человеком, сидящим внутри, а сложным механизмом.

На этих альбомах Iron Maiden стали значительно меньше внимания уделять шокирующе-мистической тематике, за которую подвергались критике со стороны религиозных организаций. Преобладать в лирике стали темы фантастики и истории. Песня To Tame a Land была написана по мотивам «Дюны» Фрэнка Херберта, Trooper содержала сюжет о Крымской войне, Where Eagles Dare и Aces High повествовали о событиях Второй мировой войны и т. д.

В конце 1980-х Iron Maiden отошли от агрессивного звучания к более экспериментальному на альбомах Somewhere in Time и Seventh Son of a Seventh Son. Seventh Son… стал полу-концептуальным альбомом. Хотя в отличие от аналогичных работ Blind Guardian и Manowar альбом не содержал подробного сценария и текстовых интерлюдий, тексты песен этого альбома складываются в рассказ о жизни ребёнка, наделённого провидческими способностями и страдающего от этого. Альбом основан на книгах фантаста Орсона Скотта Карда. В отличие от предыдущего альбома, где музыканты использовали гитарные синтезаторы, на новом релизе были использованы клавишные. Seventh Son of a Seventh Son был назван критиками «более доступным» творением коллектива, чем их предыдущая работа.