1999. februárjában Blaze Bayley közös megegyezéssel elhagyta az Iron Maident. A rajongókat sokkolta a bejelentés, hogy a volt énekes, Bruce Dickinson és a volt gitáros, Adrian Smith együtt tért vissza a bandába, ami azt jelentette, hogy a 80-as évek beli felállás állt újra a színpadon, azzal a különbséggel, hogy Janick Gers maradt harmadik gitárosként.
Az első közös stúdióba vonulás eredménye lett 2000-ben a Brave New World album. Egy progresszívabb szakasz indult el ezzel az Iron Maiden történetében. 2001. január 19-én a banda 250 000 rajongó előtt játszott Brazíliában a Rock In Rio fesztiválon. 2002. márciusában került kiadásra a videó Rock In Rio címmel.
2003-ban jelent meg a Maiden Dance Of Death című albuma. 2005-ben, Németországban a Westfalenhalle arénában egy új élő DVD-t vettek fel Death on the Road címmel. 2005. augusztus 20-án egy kisebb kellemetlenség történt az Ozzfest fesztiválon Sharon Osbourne jóvoltából, mert Ozzy felesége férfi nemiszervnek titulálta Bruce Dickinsont.
2006. novemberében az Iron Maiden menedzsere Rod Smallwood bejelentette, hogy 27 év együttműködés után szakít a Sanctuary Music-kal és új céget indított Phantom Music Management névvel.
2006. őszén jelent meg az A Matter Of Life And Death, az Iron Maiden 14. stúdió albuma. Ez sem koncept album, a témája a háború és a vallás, mint a számoknak, mint a borítójának. Egy sikeres észak-amierikai és európai turnén végigjátszották helyszínenként az egész albumot. Egy esetleges élő felvétel lehetősége is szóba került a turnéról.
2006. novemberében Rod Smallwood bejelentette, hogy 27 év után szakít a Sanctuary Music-kal és új céget alapít Phantom Music Management néven.
2007-ben ismét részt vett az Iron Maiden a nagyobb fesztiválokon egész Európában. A turné június 24-én ért véget Londonban a Brixton Academy-n.
2007. szeptember 5-én bejelentésre került a Somewhere Back in Time World Tour. A setlist a 80-as évekből lesz összeállítva a Powerslave időszakra koncentrálva és az akkori színpadi megjelenésre fókuszálva. A koncertsorozat 2008. február 1-jén kezdődik Indiában. Továbbá már egy 2008-ban kiadásra kerülő DVD-re is számíthatunk a klasszikus Live After Death és Maiden England koncertekkel!