1981-ben Paul Di'Anno viselkedése már bomlasztóvá vált, amiben meghatározó szerepe volt a kokain fogyasztásának. A teljesítménye jelentősen visszaesett, mikor a banda elkezdett Amerika szerte koncertezni. 1981. végére az együttes kirúgta Di'Anno-t és elkezdett új énekes után kutatni.
1981. szeptemberében történt meg a Samson volt énekesének, Bruce Dickinson-nak meghallgatása, nem sokkal később már be is került a bandába. Egy rövidebb turnén vett részt a Maidennel, ez a soron következő album beharangozó koncertsorozata volt, ahol már játszották a Children Of The Damned, Run To The Hills, 22 Acacia Avenue és a The Prisoner számokat, ezzel megkedveltették előre a rajongókkal az együttes "új hangját".
Ez az album volt Bruce Dickinson debütáló albuma az Iron Maidennel, 1982-ben jelent meg. A korong kikövetelte magának az első helyet a brit toplistákon és a világ számos országában került a top10-be. Második alkalommal indult a Maiden világ körüli turnéra az Egyesült Államokba, Kanadába, Japánba és Ausztráliába.
1982. második felében Clive Burr otthagyta az együttest személyi okok miatt és koncertdátumok is ütköztek a terveivel. Az ő helyére a Trust egykori dobosa, Nicko McBrain került. Nemsokkal később, 1983-ban megjelent az Iron Maiden új albuma, a Piece Of Mind.
Erről az albumról a rajongók fő kedvencei a The Trooper és a Flight Of Icarus számok, amik megjelentek külön kislemezként is.
Ezen a korongon található a To Tame A Land című szám, aminek az eredeti címe Dune lett volna a könyv után, de végül jogi problémák miatt át kellett nevezni.
A Piece Of Mind sikereit követve kiadta a banda a következő albumát Powerslave címmel, 1984-ben. A rajongók kedvencei erről a korongról a 2 Minutes to Midnight, az Aces High és a Rime Of The Ancient Mariner, ami Samuel Taylor Coleridge versén alapszik.
A Maiden eddigi legnagyobb koncertsorozata követte az albumot World Slavery Tour néven, 220 fellépéssel, 13 hónapon keresztül. Ez annyira lefárasztotta az együttes tagjait, hogy utána egy fél éves szünetet kellett tartaniuk.