Þ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ð Brce 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ð “A 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. En ABNW er sennilega freskasta afurð Iron Maiden í mörg ár og nú hlýtur að fara að styttast í nýja plötu sem á að koma út þá þessu ári.