Antes de la despedida de Bruce, Iron Maiden comenzó a audicionar a distintos candidatos a reemplazarlo. Ser inglés, tener aspecto recio y desprolijo parecido al de Dickinson, mucha escena y adrenalina, y una voz interesante eran condiciones de peso para aspirar al puesto. Finalmente la balanza se inclinó por Blaze Bayley, vocalista del grupo Wolfsbane. Wolfsbane no sólo tenía cierto peso entre la audiencia heavy británica, sino que Blaze era amigo de la banda desde que ambas salieron de gira juntas en 1990. Como ya había ocurrido en el pasado y a la hora de los cambios, Iron Maiden privilegió a conocidos sobre los aspirantes ignotos.

Para el nuevo álbum la Doncella no sólo presentaba nuevo cantante, sino que también aparecía con nuevo productor. Desde 1980 cada álbum de estudio de la banda había sido producido o co-producido por Martin Birch. Pero ahora, ya retirado, se decidió que Steve podía ocupar el papel de productor junto a Nigel Green, operador de cinta en los álbumes Killers y The Number of the Beast y en la actualidad productor de su propio sello discográfico. Finalmente, luego de un año de arduo trabajo, en octubre de 1995 salió a la venta The X Factor ('El Factor x') previo inicio de la gira "The X Factour" que los llevó por primera vez a Sudáfrica e Israel. La gira también abarcó el Este de Europa (Rumania, Bulgaria, Eslovenia, Hungría, Polonia y Chequia), Europa Occidental, Estados Unidos, Mexico, Canadá, Japón y Sudamérica.

Las ventas de The X Factor no fueron malas, pero la crítica y la mayoría de los fans no lo aceptaron como sus anteriores trabajos. La banda esperaba una acogida escéptica para un disco sin Bruce Dickinson, con un Blaze Bayley cuyas cualidades vocales no encajaban en el conocido sonido Maiden. En este álbum, las canciones son más largas pero carentes de los elementos "gancheros" que hicieron famoso al grupo en los años 80. Es posible que por ello se optara por no utilizar una ilustración de portada, como ha sido siempre costumbre del grupo, a manera de expresar la nueva dirección musical que se había adoptado en el trabajo. Esta vez el fan se encuentra con una portada fotorealista en la que se ve a Eddie mientras está siendo diseccionado. El excelente trabajo de la portada y del libreto interno es obra del maestro Hugh Syme, autor también del arte gráfico de otros discos del panorama metalero como Moving Pictures, Roll the Bones o Counterparts de Rush, o también Countdown To Extinction y Youthanasia de Megadeth. Sin duda The X Factor es el disco más diferente del clásico estilo de Iron Maiden hasta el momento, pero uno de los mejor presentados.

En 1996 vio la luz Best Of The Beast, una compilación de la banda presentada en dos versiones: un disco sencillo de 16 temas o un disco doble de 27 temas. Como aliciente se incluye el tema inédito Virus grabado durante las sesiones del último disco de estudio.

Durante 1996 y 1997, en pleno boom de los videojuegos de consolas de 32 bits y de PC, Iron Maiden encarga a la empresa inglesa Virtual Studio la realización de un juego basado en su mascota, Eddie, y con temas del grupo como banda sonora, su nombre sería Melt (mirror de la antigua web oficial de Melt). El juego tendría que haber salido en dos formatos, para PC y para PlayStation. Después de varios retrasos, y aunque se llegó hacer una pre-reserva a través del club de fans oficial del grupo, el juego fue cancelado debido a la baja calidad del mismo.

A continuación de ese disco, en 1998 fue lanzado Virtual XI, que no presentó grandes novedades ni mayor repercusión. Mientras la banda gestaba este álbum, encargaron a la compañía de desarrollo multimedia Synthetic Dimension la creación de un videojuego basado en el arte gráfico que ha venido acompañando al grupo a lo largo de su carrera y que tuviera como protagonista a Eddie. El videojuego sería llamado Ed Hunter y se publicó en 1999 acompañado de un recopilatorio de 20 temas, aunque tampoco cumplió las expectativas de los videogamers.

Por ese entonces, algunos fans estaban muy disconformes con Bayley, sobre todo por su pobre actuación en vivo, y los reportes desde el seno de la banda tampoco eran buenos. Hacia el fin de 1998, el grupo finaliza su gira mundial Virtual XI Tour en apoyo al Virtual XI, luego a principios de 1999, se anunciaba la ida de Blaze, y un nuevo comienzo, muy incierto en esos momentos.

Para 1999, la Doncella tenía guardada una gran sorpresa, que muchos fans habían esperado: el retorno de Bruce Dickinson. A esto, hay que agregarle el regreso del guitarrista Adrian Smith, conformando un trío de guitarras que crearía muchas expectativas en los seguidores, especialmente por cómo sería su sonido en vivo, con los temas "clásicos".

Ese mismo año, se lanzó el juego para PC Ed-Hunter, y como promoción, se realizó la mini-gira "Ed-Hunter tour", que a la vez sirvió como "gira del reencuentro".

Una vez culminada, el grupo se abocó de lleno a la preparación del que sería a la postre, su duodécimo disco, titulado Brave New World (2000). Como novedad, además del trío de guitarras y la vuelta de Dickinson, fue la vuelta (por lo menos colaborando) de Derek Riggs en el arte de tapa. La gira de presentación incluyó varios países de Sudamérica. En su recital de 2001 en el show que la Doncella dio en el estadio del Club Vélez Sársfield en Argentina, la banda tuvo un altercado: durante la canción "The Trooper", Dickinson flameó una bandera inglesa, a lo cual el público argentino abucheó.

Durante las giras de presentación de esta placa se registró el disco "Rock in Rio" (2002) grabado durante el festival del mismo nombre en Rio de Janeiro, Brazil. Ese mismo año también se lanzó el box-set de 6 CDs "Eddie's Archive", que contiene el recital en el Hammersmith Odeon en 1981 ("Beast over Hammersmith") durante la época de Killers con Paul Di'Anno en 2 CDs, la recopilación "BBC Archives" también de dos discos, y "Best of B-Sides", dos discos con los lados B que integraron los singles de la banda.

En 2003 Iron Maiden se dedica a grabar el nuevo álbum de estudio, Dance of Death. El primer tema del disco, titulado Wildest Dreams, fue presentado un tiempo antes en la gira "Give Me Ed... Til I'm Dead" que comenzó en la ciudad española de La Coruña y en la que se grabaría el concierto en directo del festival "Rock-am-Ring" de Alemania. Posteriormente, esa grabación fue puesta en Internet, en el sitio oficial, como promoción. A continuación se lanzó el single Wildest Dreams, incluyendo una versión orquestral de Blood Brothers, y una semana después fue lanzado el tan esperado álbum.

Además del antes mencionado Wildest Dreams, se lanzó un segundo single, titulado Rainmaker, que incluye una versión orquestal del tema que da título al álbum, Dance of Death.

Nuevamente se lanzaron a una gira mundial que culminó en Japón y que se publicaría en 2005 un doble CD y DVD en directo titulado Death on the Road con el concierto de Dortmund, Alemania. Melvyn Grant, autor de la portada del disco Fear of the Dark, fue el artista elegido para realizar la portada del disco en directo Death on the road tras el rechazo de Derek Riggs debido a la presión a la que fue sometido. Como decisión, el artista no quiso realizar más portadas de Eddie para Iron Maiden, aunque sí creó una versión femenina de Eddie para el disco del grupo tributo compuesto por chicas The Iron Maidens.

Culminada la gira, fue lanzado un Souvenir EP llamado No More Lies, que además de contener 4 temas y un par de vídeos, incluye otra clase de "souvenirs" de la banda.

Finalmente, en noviembre de 2004, lanzaron un DVD doble: The Early Days, que muestra grabaciones inéditas de los primeros años, es decir, la época que va desde el primer álbum, hasta Piece of Mind. Pero lo principal del DVD es la aparición de los integrantes de la banda en el periodo 1975-1983 (incluso los que nunca llegaron a grabar un disco con Maiden). Para promocionar el DVD, se hizo en 2005 una gira que abarcó Europa y parte de América en la que sólo se interpretaron temas de los cuatro primeros discos.

En el otoño de 2006, Iron Maiden lanza su decimocuarto álbum de estudio titulado "A Matter of Life and Death". Aunque éste no es un álbum conceptual, son temas recurrentes la guerra y la religión, al igual que las carátulas e impresos.

Luego, continuó una exitosa gira en Norteamérica y Europa, en la cual tocaron el álbum en su totalidad, por primera vez en la historia de la banda. Luego de eso, la banda anunció el lanzamiento de un álbum en vivo de la reciente gira.

En noviembre de 2006, Iron Maiden y el director Rod Smallwood anunciaron que estaban cortando sus 27 años de vínculos con Sanctuary Music y han comenzado una nueva empresa llamada Phantom Music Management. Sin embargo, no se hicieron cambios significativos.

Iron Maiden grabó una sesión en directo en la Abbey Road Studios de Live From Abbey Road, en diciembre de 2006. Su ejecución se proyectó en un episodio, junto con sesiones de Natasha Bedingfield y Gipsy Kings en marzo de 2007 en Channel 4 (Reino Unido) y en junio de 2007 en la Sundance Channel (EEUU).

En 2006, la banda confirmó varios de los principales festivales en los que tocarían en el mundo que formarían la gira de A Matter of Life and Death, en la que tocaban íntegramenteel disco A Matter of Life and Death, creando cierta controversia en algunos fans que querían los clásicos de la banda. Al llegar el año 2007 la gira se denominó "A Matter of the Beast" para celebrar el 25 aniversario del álbum The Number of the Beast. La banda anunció planes para tocar 5 canciones deA Matter of Life and Deathy 5 deThe Number of the Beast como parte de sus conciertos. El 24 de junio terminó la gira con una cuota única de rendimiento en la London's Brixton Academy en la ayuda de Clive Burr MS.