En 1996, le groupe fit une autre tournée mondiale, avant de se diriger longuement en studio pour finalement sortir en 1998 : Virtual XI. Les critiques furent meilleures que le précédent, mais les ventes diminuèrent drastiquement, du moins, au Royaume-Uni. Peut-être un effet de l'absence de Dickinson...Néanmoins, la voix de Bailey n'était pas si mauvaise et Steve Harris sembla avoir réglé ses problèmes personnels.
Une année plus tard, en 1999, Bailey quitta le groupe et Iron Maiden surprit le monde de la musique: Bruce Dickinson annoncait son retour au chant et Adrian Smith reprenait sa place derrière la guitare, ranimant ainsi le line-up des beaux jours du groupe. De plus, bien qu'il eût été recruté en remplacement de Smith, il fut proposé à Janick Gers de rester dans le groupe, ce qui fit de Maiden un groupe à trois guitaristes - Smith, Murray, et Gers.
Le groupe, ainsi reformé, entreprit sur-le-champ la production de leur 12e album, Brave New World, qui sortit en 2000. Le son, les riffs et les breaks des années 80 sont très présents dans cet opus. De plus, avec cet album, une nouvelle génération d'amateur de musique metal adhéra très vite au style d'Iron Maiden. Brave New World est un des meilleurs opus du groupe, toutes époques confondues. Le groupe entreprit une autre tournée mondiale, qui se termina en 2001 avec succès dans le célèbre spectacle Rock in Rio, à Rio de Janeiro devant plus de 250 000 fans. Pour la formation, c'était un retour à la gloire.
Plus les années passaient, plus Iron Maiden était considéré comme de vieux pionniers du metal, des vétérans grandement respectés, tant par la vieille génération des années 80 que par la nouvelle des années 2000. En 2003, le groupe sortit Dance of Death, qui adopta un style plus progressif mais tout aussi explosif. L'album figura au sommet des charts dans plusieurs pays du monde entier.
Le groupe a sortit un DVD en 2005, pour le 30e anniversaire de la formation du groupe. Le DVD, du nom de The Early Days, évoque les premieres années d'Iron Maiden, soit de 1975 jusqu'à fin 1983, recouvrant les 4 premiers albums du groupe. Ce DVD est composé d'un documentaire sur les debuts d'Iron Maiden ainsi que des videos de concerts de l'époque correpondant (avec notamment le "Live at the Rainbow", premier vidéo live, filmé et commercialisé au monde en 1981).
Pour la sortie de The Early Days, le groupe entreprit une tournée mondiale, comme il l'a si souvent fait. Pour Rod Smallwood, le gérant du groupe depuis le début de la carrière du groupe, les "highlights" de la tournée étaient les suivants: "The greatest audience was Québec City. 11000 fans, tickets all sold out in a day and the loudest thing i've ever heard. Gothenburg was pretty similar; 57000 tickets sold out in a couple of hours, nine months in advance." (Classic Rock, November 2005, Issue 86). Le succès est total mais un événement marquant vint le perturber. Le groupe prenait part au Ozzfest d'Ozzy Osbourne et était les têtes d'affiches le 20 août 2005 en banlieue de Los Angeles. Suite à un arrangement avec Sharon Osbourne, la foule se mit à huer Iron Maiden et même à leur lancer des œufs. Bruce Dickinson y est alors allé d'un cinglant discours envers la conduite de Sharon. Celle-ci répliqua, peu de temps après, en prétextant régler ses problèmes avec Dickinson. Ce malheureux incident ne changea toutefois rien à la popularité d'Iron Maiden, qui aujourd'hui est toujours au sommet. D'ailleurs, la veille de cet incident, les membres du groupe ont été invités à laisser leurs empreintes de mains sur le Hollywood's Rock Walk du célèbre magasin de musique Guitar Center. Ils se retrouvent ainsi inscrit dans la légende au côté de plus de 160 autres groupes ou artistes célèbres comme par exemple AC/DC, Aerosmith, Alice Cooper, B.B. King, Black Sabbath, KISS, Jimi Hendrix, Queen ou encore Van Halen, Yes, ZZ Top, etc.
En 2005, sortit un nouvel double album live Death on the Road. Iron Maiden a également sorti en février 2006 un DVD intitulé "Death On The Road", comprenant leur concert de décembre 2003 au Westenfalenhalle Arena de Dortmund, ainsi que divers bonus.
Le nouvel album du groupe, est sorti en août 2006. "A Matter Of Life And Death", c'est son nom, comprend 10 chansons et dure près de 72 minutes. Après une participation à des festivals, une tournée européenne est d'ores et déjà programmée pour l'automne avec le groupe Trivium, qui se poursuivra en 2007 sur d'autres continents!