Nafnið á Iron Maiden var tekið af gömlu pyntingatæki sem var einskonar kassi alsettur göddum sem hinr ógæfusömu voru látnir dúsa í dögum og vikum saman. Síðar fékk Margaret Thatcher forsætisráðherra Bretlands þetta viðurnefni, en þá var hljómsveitin ekki orðin sérlega þekkt ennþá. Vegna þessa héldu sumir að þeir sæktu nafngift sína til forsætisráðherrans. En hugmyndina af nafni mun Harris hafa fengið eftir að hann sá kvikmyndina The Man In The Iron Mask.
Iron Maiden var beint framhald af því sem Harris hafði verið að gera með þeim hljómsveitum sem hann var áður í. Hann fékk fyrrum félaga sinn úr Smiler, Dennis Wilcock til að koma sem söngvari. Wilcock stakk upp á því að þeir réðu David Murray sem gítarleikara, en hann hafði verið í hljómsveit sem Wilcock hafði verið í og hét Warlock. Annar gítarleikari var ráðinn, en sá hét Bob D\'Angelo. Trommari var Ron Matthews. Vegna þess að Murray samdi ekki við D\'Angelo og Wilcock var hann rekinn eftir nokkra mánuði. Murray fór þá í hljómsveitina Urchin með æskuvini sínum Adrian Smith og þeir gáfu stuttu síðar út litla plötu.
Þegar Murray fór úr Maiden var ákveðið að ráða hljómborðsleikara í staðinn. Það gekk engann veginn upp og hann var látinn hætta ekki löngu síðar og um skeið voru þeir bara fjórir. Næstu mánuðina gekk á ýmsu og að lokum var söngvaranum Wilcok sparkað ásamt Matthews trommara og Bob D\'Angelo gítarleikara. Í staðinn voru ráðnir söngvarinn Paul Di\'Anno, Trommarinn Doug Sampson og Dave Murray var endurráðinn því að Harris sagðist ekki geta séð af svo góðum gítarleikara. Murray er síðan eini maðurinn fyrir utan Harris sem hefur starfað í Maiden allar götur síðan.
Á þessum tíma var pönkið alsráðandi, en Harris og félagar hlustuðu einnig mikið á þungarokkssveitir eins og Deep Purple, Thin Lizzy, Judas Priest og Ufo. Tónlistin hjá Maiden var á þessum tíma þungarokk eða metal með smá pönklegu ívafi og söngurinn hjá Di\'Anno gaf þessu líka dálítnn pönk stíl. Svona kom hljómsveitin fram í fyrsta sinn í Ruskin Arms klúbbnum í London á gamlaársdag 1977, en Harris hefur alltaf talið það byrjunarreit Iron Maiden.
Eftir að hafa náð dálitlum vinsældum í klúbbum í East End og svæðinu í kring, þá ákváðu þeir að leigja stúdíó í einn dag og taka upp lög sem samin höfðu verið. Þeir tóku upp lögin Prowler, Invasion, Strange World og Iron Maiden. Þeir sendu upptökurnar til plötufyrirtækja og fengu þær gefnar út á lítilli plötu sem hét The Soundhouse Tapes. Hún var gefin út í litlu upplagi 1979 og gersamlega ófáanleg í dag.
Þetta vakti athygli ýmissa aðila og umboðsmaðurinn Rod Smallwood (sem þeir uppnefndu Smallwallet) tók við umboðsmálunum hjá þeim. Þeir komust einnig í tengs við listamanninn Derek Riggs sem hannaði merki handa þeim og teiknaði fígúruna Eddie sem hefur verið á öllum plötum þeirra síðan.
Þeir fengu í framhaldi plötusamning við EMI útgáfuna. Stuttu síðar var ákveðið að bæta við öðrum gítarleikara að hugmynd Smallwood og þá var ráðinn Dennis Stratton. Um það leyti hætti Doug Sampson trommari vegna veikinda og í hans stað kom Clive Burr. Svona skipað tók bandið upp sína fyrstu plötu. Á þessum tíma var metal í mikilli uppsveiflu í Bretlandi og undanfarið ár hafði töluvert að plötum í þeim geira gert það gott. Í mars kom út fyrsta lagið af fyrstu plötunni en það var Running Free. Það komst í 36. sæti á vinsældalistnum í Bretlandi og í kjölfarið var þeim boðið að spila í Top Of The Pops þættinum í BBC. Þeir neituðu hinsvegar að koma fram nema þeir fengju að flytja lagið live, því að þaim fannst aulalegt að standa og “mæma”. Það var að lokum fallist á það og þeir urðu fyrsta hljómsveitin til að koma fram live í þættinum síðan Who gerði það 1973.
Platan kom síðan út 14. apríl 1980. Hún fékk einfaldlega nafnið “Iron Maiden” og á umsalginu var fyrsta útgáfan af Eddie sem teiknuð hafði verið af Derek Riggs. Hann var dálítið öðruvísi á þessari mynd er síðar varð og á síðari útgáfum af þessari plötu hefur honum verið breytt dálítið. Platan var hrá með dáltilu pönk yfirbragði og á henni var m.a. að finna þrjú af þeim lögum sem höfðu komið út á Soundhouse Tapes árið áður.
Með þessari plötu töldu margir að fædd væri ný stefna sem Geoff Barton blaðamaður á Sounds og síðar ritstjóri Kerrang hafði árið áður kallað NWOBHM eða New Wave Of British Heavy Metal. Metal var aftur komið á kortið og árið 1980 ári kom út fjöldi platna með með hljómsveitum sem flokkuðust undir þessa stefnu. Sumar þeirra voru nýjar en aðrar voru eldri og höfðu öðlast nýtt líf. Svo einkennilegt var það á þessu ári, að margar eldri hljómsveitir gáfu út sínar bestu plötur í áraráðir. Sum laganna af fyrstu plötunni hafa fylgt Maiden alla tíð eins og Prowler, Running Free, Phantom Of The Opera og Iron Maiden. Platan náði 4 sæti á vinsældalistanum í Englandi.
Þetta sama ár komu einni út tvær aðrar litlar plötur með þremur lögum hvor. það voru Sanctuary og Women In Uniform. Umslögin á báðum þessum smáskífum öllu töluverðum deilum því að á því fyrra sást Eddie myrða Margaret Thatcher með öxi, en á því síðara náði hún fram hefndum því að hús sat fyrir Eddi vopnuð vélbyssu. Þetta varð auðvitað bara til þess að vekja meiri áhuga á bandinu. Maiden hafa alla tíð verið duglegir við að gefa út smáskífur með lögum sem ekki var að finna á stóru plötunum og oft var um að ræða lög eftir aðra. Í árslok 1980 hætti Dennis Stratton gítarleikari, en hann var dálítið eldri en hinir í bandinu og passaði einhvernveginn aldrei inn í félagskapinn. Í hans stað var ráðinn Adrian Smith æskuvinur Dave Murray.
Þegar næsta plata var í bruðarliðnum var ljóst að það þyrfti að vanda vel til verka því að efniviðurinn var til staðar til að gera mikið úr bandinu. Upptökustjóri var fenginn Martin Birch, en hann hafði m.a. verið við upptökur á mörgum plötum Deep Purple og verið upptökustjóri hjá Black Sabbath, Rainbow, Whitesnake og fleiri þekktum hljómsveitum. Hann breytti sándinu, þétti það og pússaði til. Trommurnar voru líka áberandi framar og bassaleikur Harris naut sín betur en á fyrstu plötunni. Í raun má segja að Birch hafi búið til þetta Iron Maiden sánd sem þeir hafa allar götur síðan verið þekktir fyrir. Platan kom út í febrúar 1981 og hét “Killers” Hún fékk góðar viðtökur og Maiden voru þegar krýndir konungar NWOBHM. Hæst náði platan 12 sæti á vinsældarlista í Bretlandi. Hún seldist í upphafi miklu betur en fyrsta platan en þegar fram liðu stundir reyndist sú fyrsta lífseigari. Það voru mörg frábær lög á Killers, en aðeins Wrathchild og í seinni tíð Killers hafa lifað af þeim. Martin Birch sagði í viðtali á þessum tíma að Iron Maiden hefðu í sínum huga tekið þann sess sem Deep Purple höfðu áður og það væri margt líkt með að vinna með þessum tveimur hljómsveitum.
Á eftir Killers fylgdi stór hljómleikaferð um allan heiminn þar sem þeir ýmist hituðu upp fyrir sveitir sem höfðu náð að tryggja sig betur í sessi eins og Kiss og Judas Priest eða voru sjálfir aðalnúmerið eins og í Japan. Þar var tekin upp lítil hljómleikaplata með fjórum lögum og gefin út þar í landi. Hún hét Maiden Japan og var vísað til frægrar hljómleikaplötu Deep Purple, Made In Japan.
Það var ljóst að næsta plata Iron Maiden yrði afar þýðingarmikil því að húnn myndi ráða því hvort þeir næðu að slá almennilega í gegn. Fræjunum var sáð, en það vantaði ennþá töluvert á frægðina. Á árinu 1981 spiluðu þeir á 125 hljómleikum og það hefur alltaf verið eitt aðalsmerki þeirra hversu duglegir þeir hafa verið við að spila vítt og breytt. Paul DiAnno söngvari lifði hátt og skemmti sér mikið og það tók sinn toll. Hann var með fremur viðkvæma rödd og skemmtilífið, miklar reykingar og áreynsla vegna hljómleika ollu því að röddin í honum var farin að gefa sig á köflum. Það þurfti að fresta nokkrum hljómleikum vegna þessa og hann reyndi lítið að bæta úr þó að læknar sögðu honum að ef hann ætlaði að halda röddinni yrði hann að hætta að reykja og drekka ekkert strekara en te. Það kom að því að félagar hans gáfust upp og hann var rekinn haustið 1981.
Þetta olli ákveðinni óvissu. Að vísu var strax tilkynnt að nýr söngvari hefði verið ráðinn en það var alltaf erfitt að skipta um söngvara, því að hann gefur tónlistinni ákveðinn karakter. Þegar þeir leituðu að eftirmanni Di\'Anno þá fóru þeir ekki langt yfir skammt sem fyrr. Sá sem var valinn hafði verið í hljómsveitinni Samson, en Clive Burr trommari Maiden hafði verið þar nokkrum árum áður. Söngvarinn gekk undir nafninu Bruce Bruce en hét réttu nafni Paul Bruce Dickinson.
Þeir spiluðu á nokkrum tónleikum áður en upptökur hófust á nýrri plötu og þóttu tónleikarnir tekast afar vel. Dickinson féll mjög að eldri lögunum og gaf þeim nýtt líf. Upptökur á nýju plötunni hófust snemm árið 1982 og hún kom út í lok mars 1982. Platan hét “The Number Of The Beast” og titillagið hófst á ritningarlestri úr Biblíunni þar sem lesinn var spádómurinn um Andkrist (the beast). Það var undarlegt að lagaröðinni á plötunni var oft breytt síðar þannig að hún hófst á titillaginu, en upphaflega var Invaders fyrsta lagið. Áður en platan kom út var lagið Run To The Hills gefið út á smáskífu. Það fékk mjög góðar viðtökur og því var plötunnar beðið með mikill eftirvæntingu og hún rauk strax í efsta sætið í Bretlandi.
Margir telja þetta hafa verið bestu plötu Maiden frá upphafi og vissulega fékk hún sess sem klassísk metal plata. Kraftmikil lög frábært sánd, þungur trommuleikur og öflugur bassi. Söngur Bruce Dickinson eins og hann kallaði sem nú var fyrsta flokks. Platan innsiglaði frægði Iron Maiden og það var þegar vitað að það yrði erfitt að fylgja henni eftir.
Á hljómleikaferðinni á eftir Number Of The Beast spilaði hljómsveitin á rúmlega 150 hljómleikum. Álagið af eilífum ferðalögum og ýmiskonar erfiðleikar í samskiptum við Harris urðu til þess að þegar ferðinni lauk haustið 1982 þá sagði Clive Burr trommari starfi sínu lausu og hætti. Það liðu nokkrar vikur þar til tilkynnt var um eftirmann hans, en það kom nokkuð á óvart því að sá sem var ráðinn var lítið þekktur trommari að nafni Michael McBrain, sem hafði verið stuttan tíma í frönsku hljómsveitinni Trust sem gáfu út nokkrar fínar plötur í kringum 1980. Hann hafði kynnst Steve Harris og félögum þegar Trust hitaði upp fyrir Maiden árið 1981. Margir töldu í fyrstu að hann væri franskur vegna þessa og auk þess sem hann var kallaður Nicko, sem hefði getað verið franskt nafn. Hann var hinsvegar fæddur og alinn upp í London eins og hinir í Maiden og hafði kynnst Trust í gegnum sessionvinnu. Fljótlega eftir að hann var ráðinn í ársbyrjun 1983 fór bandið til Bahamaeyja til að vinna hið erfiða verkefni að fylgja The Number of the Beast eftir.
Það fannst mörgum missir að Clive Burr, Hann var nokkuð sérstæður trommari sem gaf sándinu ákveðinn karakter og mörgum fannst sándið hjá hljómsveitinni aldri verða samt aftur. McBrain var hinsvegar afburða trommari og hann sannaði það þegar næsta plata kom út í maí 1983. Það hafði jafnvel verið beðið eftir henni með enn meiri eftirvæntingu en Beast. Stuttu áður en platan kom var lagið The Flight of Icarus gefið út á smáskífu. Platan fékk nafnið “Piece Of Mind” eða “stykki úr huganum” en í framburði gat það líka útlaggst sem Peace Of Mind eða “sálarró”. Myndin á umslaginu kom nokkuð á óvart því að þar var Eddie hlekkjaður niður á geðveikrahæli. Það voru ekki allir sáttir við plötuna og lagasmíðarnar og hún fékk bæði góða og slæma gagnrýni. Helst var sett útá það að lagasmíðarnar væru ekki eins öflugar og áður, en platan vann fjölda nýrra fylgjenda og fór í 3. sæti á vinsældalista í Bretlandi og 14 í Bandaríkjunum.
Síðasta lag plötunnar var langt epískt lag og hét To Tame A Land. Upphaflega átti lagið að heita Dune eftir vísindaskáldsögunni þekktu sem hefur m.a. verið kvikmynduð. Á þessum tíma var David Lynch að undirbúa mynd eftir sögunni og þegar það fréttist að lagið ætti að heita Dune var þegar í stað hótað málssókn. Nafni lagsins var breytt, en það tókst ekki í öllum tilvikum að breyta miðanum á plötunni og þar stóð í mörgum útgáfum plötunnar að lagið héti Dune. Annað lag á plötunni var samið undir áhrifum frá bók, en það var Where Eagles Dare eða Arnarborgin eftir Alistair McLean.
Hljómleikaferðin á eftir gekki frábærlega og showið á sviðinu var stöðugt að aukast. Þeir spiluðu á rúmlega 180 hljómleikum á 8 mánaða tímabili. Þeir tóku sér dálítið frí áður en upptökur hófust á næstu plötu. Það tafðist töluvert að gefa hana út af ýmsum orsökum og þegar hún kom út í september 1984 þá voru þeir þegar búnir að vera í mánuð á hljómleikaferð þar sem þeir spiluðu m.a. víða um Austur Evrópu. Platan fékk nafnið “Powerslave”. Áður en hún kom út var eins og venjulega gefin út smáskífa með laginu Two Minutes To Midnight sem var vísan til dómsdagsklukkunar frægu sem tímaritið Atomic Science Bulletin birtir reglulega sem mælikvarða á það hversu mikil hætta sé á kjarnorkustríði. Önnur lög sem fengu mikla spilun voru Aces High sem fjallaði um orrustuna um Bretland og síðan titillag plötunnar Powerslave. Á umslagi plötunnar var Eddie orðinn að egypskum guði og honum hafði verið reist musteri. Nafnið á plötunni vísaði líka til þess að þegar egyspku faraóarnir dóu, þá voru oft þúsundir þræla grafnir lifandi með þeim í píramýdunum. Það vakti töluverða athygli að logkalagið á plötunni var um 15 mínútna langt og samið með kvæðið um sjómannin og albatrossinn í huga. Það var orðin venja að enda plöturnar með löngum lögum en þarna náði það eiginlega hámarki. Þrátt fyrir lengd lagsins varð það fastur liður á hljómleikum um langt skeið.
Það má kannski segja að á þessum tíma hafi vinsældir Iron Maiden verið hvað mestar. Hljómsveitin setti þá met þegar hún spilaði fjögur kvöld í röð fyrir fullu húsi í Long Beach Arena í Los Angeles. Það hafði ekki verið gert áður Þeir hljómleikar voru bæði teknir upp og kvikmyndaðir og það var gefið út að næsta plata yrði hljómleikaplata. Á þessum tíma kom líka upp einkennileg saga þess efnis að lesa mætti sögu hljómsveitarinnar úr plötuumslögum þeirrar. Á fyrstu plötunni var Eddie hrár og óreyndur. Á annarri var hann búinn að greiða sér og farinn að höggva mann og annnan og á Beast var hann orðinn risastór. Síðan kom óvissutímabil og Eddie var lokaður inni, en þegar Powerslave kom út þá var hann orðinn guð. Hvort Derek Riggs hugsaði þetta svona er erfitt að segja til um, en hugmyndin er skemmtileg.
Hljómleikaferðin á eftir Powerslave var gríðarleg. Hún tók um 13 mánuði og bandið spilaði á yfir 300 hljómleikum. Það var orðið tímabært að gefa aðdáendum sveitarinna tækifæri til að hlusta á hljómsveitina á liveplötu og síðan hitt að þeir voru eiginlega komnir í mikla þörf fyrir hvíld.
Hljómleikaplatan “Live After Death” kom út í október 1985. Hún var tvöföld og vandaður pakki, því að það fylgdu með textar allra laganna á henni sem var óvenjulegt með hljómleikaplötur og stór og mikill bæklingur með myndum úr túrnum. Ásamt plötunni kom út vídeó með sömu lögunum að mestu leyti. Sviðið á túrnum var býsna áhrifamikið og með egypskum blæ. Í lokin opnaðist gyllt stytta af Eddie sem var aftan við hljómsveitina og út kom hann risastór vafinn eins og múmía. En það var ljóst að þeir myndu aldrei fara í aðra eins ferð og slavery túrinn, því að í lokin voru þeir orðin svo lúnir og leiðir á hverjum öðrum að bandið var við það að liðast í sundur.
Næasta plata þeirra kom út í júní 1986 og fékk nafnið “Somewhere In Time”. Þá var Eddie orðinn cyborg og flaug um á geimskipi. Á umslaginu var Eddie var staddur í einhverri stórborg og þar mátti lesa ýmsilegt sem vísaði í sögu hljómsveitarinnar. Það mátti lesa fréttir um stórsigur West Ham og klukkuna vantaði 2 mínútur í miðnætti, auk þess sem skemmtistaður á myndinni hét Ruskin Arms svo nokkuð sé nefnt. Platan seldist mjög vel eins og síðustu plötur, en engu að síður fékk hún á sig töluverða gagnrýni. Þarna notaði hljómsveitin synthesizera í fyrsa sinn, en það sem aðallega var gagnrýnt var það að lögin væru samin eftir staðnaðri formúlu sem væri búið að margreyna áður. Flest lögin voru nokkuð löng og þau sem fengu mesta spilun voru Wasted Years og Stanger In A Strange Land.
Það leið nokkuð langur tími þar til næsta plata kom út og í fyrsta sinn liðu tvö ár á milli platna, en þeir höfðu alltaf gefið út plötu á hverju ári síðan sú fyrsta kom árið 1980. Sú næsta kom í maí 1988 og fékk nafnið “Seventh Son Of A Seventh Son” og var þar vitnað til þess að hún var númer sjö í röðinni. Hugmyndin í kringum plötuna var um lífið frá fæðingu, til dauða og afkomendurna sem síðan taka við. Platan var óneitanlega með dálítið svipuðum blæ og Somwhere og hún fékk líka samskonar gagnrýni frá mörgum. Lögin væru samin eftir formúlu og fátt nýtt að finna. En platan seldist engu að síður vel.
Það var ljóst að eftir Seventh væri bandið á ákveðnum tímamótum og eftir þetta lá leiðin niðurávið af ýmsum orsökum. Bæði var komin þreyta í samstarfið og menn heldur ekki allir á einu máli um hvaða stefnu skyldi taka í framtíðinni. Það voru komnar fram margar nýjar hljómsveitir sem urðu vinsælar og metal heimurinn var á breytast. Það má líka segja að hvaða skoðun sem menn hafa á Iron Maiden, þá var hljómsveitin komin í ákveðna þurrð með hugmyndir.
Á umslagi Sewneth var Eddie að leysast í sundur og mátti eiginlega lesa það þannig að nú væri kominn tími til að breyta um og taka nýja stefnu. Það var ákveðið að taka algerlega frí frá hljómsveitinni í eitt ár og athuga hvort menn kæmu ekki ferskir til baka.
Þegar Iron Maiden tóku sér ársfrí, þá fóru félagarnir að bisa við ýmsilegt sitt á hvað. Það var þó aðeins Bruce Dickinson sem gaf út eitthvað efni, en hann sendi frá sér sólóplötuna “Tattooed Millionare” árið 1990, þar sem hann vann m.a. með gömlum kunningja þeirra í Maiden að nafni Janick Gers, sem hafði áður verið m.a. í hljómsveitinni Gillan ásam Ian Gillan söngvara Deep Purple. Adrian Smith stofnaði einnig hljómsveitina ASAP (as soon as possible). Þeir tóku hinsvegar ekkert upp á þessum tíma. Meðan á hvíldartímanum stóð lagði Steve Harris hausinn í bleyti og áttaði sig á því hvert bæri að stefna, því að bandið var að mörgu leyti komið á endastöð. Hann ákvað að hverfa aftur til upphafsáranna aftur hvað varðaði sánd og lagasmíðar. Martin Birch var enn einu sinni ráðinn sem upptökustjóri til að stjórna næstu plötu.
Þegar upptökur hófust sumarið 1990, þá kom í ljós að það var ekki einhugi innan hljómsveitarinnar um þetta og því lauk með því að Adrian Smith gekk út og sagðist hættur. Þá hringdi Bruce í sinn gamla félaga Janick Gers og bauð honum að taka sæti Smith. Það reyndist afar vel því að Gers kunni flest Maidenlögin og hafði margoft spilað þau. Hann spilaði að miklu leyti á plötunni, en eitthvað af efninu hafði þegar verið tekið upp áður en Adrian Smith hætti.
Platan kom út 1. október 1990 og fékk nafnið “No Prayer For The Dying”. Hún fékk blendna dóma. Margir sögðu að þar væri fátt nýtt að finna en margir aðrir tóku henni vel. Allavega var salan góð og lögin Holy Smoke, Tailgunner og sérstaklega Bring Your Daughter To The Slaughter, gerðu það gott. Það síðastnefnda náði m.a. efsta sæti vinsældalistans í Bretlandi. Lagið var samið af Dickinson minnti nokkuð á sumt af því sem hann hafði verið að gera á sóloplötu sinni. Það var margt öðruvísi en áður á hljómleikaferðinni sem fylgdi. Nú var sviðið t.d. líkara því eins og var á Killers hljómleikaferðinni. Bara svið og magnarar og minni effektar.
Þeir fóru að vinna að næstu plötu snemma árið 1992. Nú var Steve Harris í fyrsta sinn upptökustjóri ásamt Birch. Dickinson samdi líka töluvert á þessari plötu eins og á NPFTD. Hún kom út í maí 1992 og fékk nafnið “Fear of The Dark”. Af henni náði lagið Be Quick Or Be Dead töluverðum vinsældum í Bretlandi. Þetta ár voru þeir í annað sinn aðalhljómsveitin á Donington hátíðinni. Á þessum hljómleikum kom Adrian fram með þeim í einu lagi, svona til að sýna að það andaði ekkert köldu á milli þeirra. Þeir hljómleikar voru bæði hljóðritaðir og kvikmyndaðir tl útgáfu síðar.
Stuttu eftir hljómleikana í Donington Park kom hljómsveitin til Íslands. Að vísu kannski 10 árum of seint en spiluðu samt á fínum hljómleikum í Höllinni.
Í ársbyrjun 1993 tilkynnti Bruce Dickinson mörgum að óvörum að hann væri hættur í Iron Maiden. Hann hafði verið að hugsa um þetta í nokkur ár og skilnaðurinn var í góðu. Hann hélt áfram að starfa með þeim í nokkra mánuði eftir þetta. Hann gaf þá skýringu að hann vildu reyna eitthvað nýtt og hefja sólóferil sinn að nýju, auk þess að eyða tíma með fjölskyldunni. Hann gerði sér síðan lítið fyrir og gaf út 7 plötur á næstu 8 árum þar sem m.a Adrian Smith spilaði með honum. Það var ákveðið að taka upp hljómleikaplötu sem kveðjuplötu fyrir Dickinson. Platan kom síðan út í október 1993 og hét “A Real Live Dead One”. Það ótrúlega var að mánuði seinna voru upptökurnar frá Donington árið áður gefnar út undir nafninu “Live At Donington”. Það má því segja að Bruce hafi verið kvaddur með stæl.
Nú hófst mikil leit að nýjum söngvara. Það er sagt að þeir hafi fengið sendar tæplega 5000 upptökur á meðan á leitinni stóð. Að lokum fóru þeir ekki langt yfir skammt í mannavali eins og svo oft áður og völdu Bayley Cook sem notaði nafnið Blaze Bayley og var söngvari Wolfsbane sem höfðu hitað upp hjá þeim þremur árum áður. Blaze þótti minna nokkuð á Bruce í útliti og ekki vera ósvipaður söngvari. Það liðu rúm tvö ár þar til fyrsta afurðin með Blaze leit dagsins ljós. Það urðu margvíslegar tafir á starfi þeirra og m.a. slasaðist Bayley í mótórhljólaslysi um það leiti sem upptökur áttu að hefjast. Platan kom út í október 1995 og fékk nafnið “The X-Factor” Þar stóð X m.a. fyrir 10 en þetta var tíunda stúdíóplata þeirra. Það mun einnig hafa komið til greina að kalla plötuna The Xecution of Eddie en fallið var frá því. Á X var Steve Harris upptökustjóri ásamt Nigel Green sem hafði verið aðstaðarmaður Martin Birch á mörgum platna IM. Birch settist hinsvegar í helgann stein.
The X Factor fékk ekki góðar viðtökur. Vissulega voru flestir sammála um að á henni væru margar góðar lagasmíðar, en það fannst flestum eitthvað vanta og Bayley var ekki jafn mikill karakter og Bruce og gaf bandinu lítið líf, enda var kannski líka erfitt fyrir hann að koma svona inn. Hljómleikaferðin á eftir þótti hinsvegar takast býsna vel.
Árið 1996 var gefin út “best of plata” en þeir fóru að vinna að næstu stúdíóplötu eftir gott frí árið 1998. Platan kom út mars það ár og fékk nafnið “Virtual XI” Í nafninu var vísað til þess að þetta væri 11 afurð þeirra úr stúdíóinu og einnig þess að hún væri beint framhald af X-Factor. Virtual, fékk eins og fyrirrennarinn blendnar viðtökur og margir á því að þetta væri slakasta plata þeirra og margir töldu að endirinn væri að nálgast hjá Iron Maiden.
Á hljómleikaferðinni sem fylgdi gekk allt á afturfótunum m.a. vegna veikinda Bayley sem talið er að hafi verið tengd sukki og margt þótti minna á dagana áður en DiAnno var rekinn. Það var líka stöðugur orðrómur í gangi um að bandið væri að leysast upp, að Bayley og Harris töluðu ekki saman og Bayley ferðaðist í annarri rútu á ferðalögum. Sá orðrómur var ekki ástæðulaus, því að í febrúar var tilkynnt að Bruce Dickinson væri aftur orðinn söngvari Iron Maiden og Adrian Smith væri líka á ný kominn inn í bandið, nú sem þriðji gítarleikari. Það var nánast ekkert fjallað um Bayley, rétt eins og hann hafi aldrei verið til. Bayley hefur hinsvegar sjálfur sagt að þetta hafi verið on good terms.
Síðar á árinu fóru þeir að undirbúa plötu sem var beðið með nokkurri eftirvæntingu. Hún kom út í maí 2000 og fékk nafnið “ Brave New World” eftir skáldsögu Aldous Huxley. Þegar fyrsta lagið The Wicker Man hófst, þá vissu Maiden aðdáendur að Iron Maiden væri komin aftur. Á Plötunni er bæði afturhvarf til gömlu daganna og líka margt sem minnir á nýrri plötur þeirra. Nú er komin ný plata og heitir hún Dance of Death.
Hérna er svona smá um Strákana og Störf þeirra
Bruce Dickinson
Fæddur – Paul Bruce Dickinson - 7 ágúst 1958, fæddist í Workshop.
Byrjaði í Iron Maiden – 1982
Staða – Giftur og þrjú börn.
Fyrrverandi hljómsveitir – Samson
Stíll – Frægur fyrir mjög háar raddsveiflur.
Bruce er flugmaður að mennt( Flýgur fyrir ICELAND EXPRESS ) hann er líka með háskólagráðu í sagnfræði og mannkynssögu, hann hefur tekið fimm áfanga í óperusöng. Kennir skylmingar.
Steve Harris
Fæddur – Steve Harris 12 mars 1956 í Leytonstone Englandi.
Stofnaði Iron Maiden.
Staða – Fráskilin og tvö börn.
Fyrrverandi hljómsveitir – Gypsy Kiss, Smiler.
Steve þótti efnilegur í fótbolta á árum áður.
Spilar á bassa.
Dave Murray
Fæddur – David Michael Murray 23.desember 1956.
Byrjaði í Maiden – 1977
Staða – Giftur og tvö börn.
Fyrrverandi hljómsveitir – Stone Free, Electric Gas, Legend, The Stuff, Evil Ways
Spilar á gítar.
Adrian Smith
Fæddur – Adrian H. Smith 27 febrúar 1957.
Byrjaði í Iron Maiden – 1981
Staða – Giftur og tvö börn.
Fyrrverandi bönd – Urchin, Evil Ways, ASAP
Spilar á gítar.
Janick Gers
Fæddur – Janick Gers 27 janúar 1957
Staða – Giftur og fjögur börn.
Byrjaði 1990
Spilar á gítar.
Nicko McBrain
Fæddur – Michael McBrain 5 júní 1954.
Byrjaði 1983
Staða – Giftur og tvö born.
Fyrrverandi bönd – Trust.
Spilar á trommur, hann er áhugaflugmaðu
I will never doubt the power of those in love.
Hugi notar vefkökur til að bæta notendaupplifun á vefsíðunni og greina umferð um hana.
Einnig hefur Hugi uppfært persónuverndarstefnu sína.