1991-1995
1992 - É lançado o 9º álbum de estúdio: "Fear of the Dark", um regresso dos Maiden aos 1ºs lugares das tabelas de vendas. Em Portugal, na semana de lançamento, o álbum chegou ao 4º lugar. Esteve cerca de 7 semanas entre os 20 álbuns mais vendidos. Foram extraídos os singles "Be Quick or Be Dead", "From Here to Eternity" e "Wasting Love".
1993 - São lançados 2 álbuns ao vivo, em separado: "A Real Live One" e "A Real Dead One", num curto espaço de 2 meses a separá-los. o 1º chega ao 10º lugar, com o tema "Fear of the Dark" como grande bandeira. O 2º chegou ao 12º lugar e esteve cerca de 4 semanas na tabela de vendas lusa, dos 20 primeiros lugares. Na reedição dos álbuns, em 1998, a editora optou por juntá-los num duplo CD: "A Real Live Dead One". No mesmo ano, é editado outro registo ao vivo, duplo, intitulado: Live at Donigton", com fundo branco e letras a preto. Em 1998, foi reeditado, com uma capa modificada. A capa original tornou-se objecto de colecionador.
- É lançado o VHS "Raising Hell", que até hoje ainda não conheceu o formato DVD. Último show de Bruce Dickinson com a Dama de Ferro e que conta com a participação especial do ilusionista Simon Drake. No final do show, e relativamente ao tema "The Number of the Beast" é notório o alívio de Bruce, quando afirma: "Pronto! Já não tenho de cantar mais isto!" Era sinal de que Bruce estava mesmo desejoso de sair, por estar saturado. Aliás, em grande parte dos shows dessa Tourné, quando os mesmos terminavam, instalava-se um silêncio profundo.
- Bruce Dickinson deixa os Iron Maiden, dedicando-se por inteiro à sua carreira a solo. Steve Harris começa a busca por um substituto.
1994 - Blaze Bayley é o vocalista escolhido para substituir Bruce Dickinson, que tinha deixado a banda um ano antes. Pouco depois da sua entrada, teve um acidente de moto, que o obrigou a estar 6 meses em recuperação.
1995 - É lançado o 10º álbum de originais, o primeiro com Blaze como vocalista: "The X-Factor", um registo algo diferente do habitual, com a banda a adaptar a sonoridade à voz do novo vocalista. Na semana de lançamento, chega ao 5º lugar em Portugal e o single de lançamento, "Man on the Edge" começa a dar cartas, chegando inclusivé ao 1º lugar dos tops na Finlândia e ao 10º no Reino Unido. "Lord of the Flies" é o single que segue, filmado em Israel, com imagens ao vivo e do país em si. No entanto, muitos fãs ficam desagradados com o novo frontman e só mesmo o 1º single é que os faz ter uma visão do passado recente. No entanto, o álbum é bem recebido em alguns países nórdicos, nomeadamente a Finlândia, onde chega ao 2º lugar e a Suécia, onde se fixa no 4º posto. No Reino Unido, chega ao 8º lugar das tabelas de vendas.O quinteto embarca na "The X-Factour", que passa por Portugal, em Outubro de 1995, no Pavilhão Dramático, em Cascais.
1996 - É lançada a 1ª compilação da banda "The Best of the Beast", em registo duplo, com algumas preciosidades: um tema novo, "Virus", um tema da era Dickinson ao vivo, cantado por Blaze, "Afraid to shoot Strangers" e as 4 faixas do EP "The Soundhouse Tapes". A compilação abarca na totalidade, todos os álbuns da banda, nomeadamente, os temas mais mediáticos e mais bem sucedidos nas tabelas de vendas e com a particularidade de ser em contagem decrescente: da actualidade até ao início.