The Soundhouse Tapes (1978-79)

Em 1978, Harris encontrou um novo vocalista: Paul Dianno. A banda sempre rejeitou o punk, mas com a chegada de Paul Dianno, que era um fã de Pistols e Clash e um dos poucos membros de Maiden que tiveram cabelo curto, o Maiden precisou abrir sua sonoridade para músicas mais rápidas e mais diretas, procurando focar no heavy metal que renascia mesmo que timidamente. Durante anos a banda foi pressionada pelas gravadoras para cortar seu cabelo e sacrificar o som do metal (segundo as mesmas) a favor de uma imagem mais punk. Mas com Dianno como líder, a banda pôde mixar os dois estilos e fazer um próprio, juntando o metal com o punk. Eles misturavam temas clássicos, ritmos de metal empolgantes e riffs de guitarra bem hardcore e rápidos.
O Iron Maiden foi a sensação do circuito do rock inglês de 1978. A banda tocava sem parar havia três anos ganhando um tremendo número de fãs, mas mesmo assim até essa época, eles nunca tinham gravado nada. No ano novo de 1978, a banda gravou uma das mais famosas demo tapes da história do rock, The Soundhouse Tapes. Com apenas três faixas, a banda vendeu todas as cinco mil cópias imediatamente, e não distribuiu a demo novamente até 1996. Cópias da versão original são vendidas hoje em dia por milhares de dólares. Duas das faixas da demo, "Prowler" e "Iron Maiden", ficaram em primeiro lugar nas paradas de metal inglesa.
Em muitas das formações antigas do Iron Maiden, Dave Murray era acompanhado de outro guitarrista, mas grande parte de 1977 e todo o ano de 1978, Murray foi o único guitarrista do Maiden. mas durante o ano de 1979 a banda teve vários segundos guitarristas sucessivos, tais como Paul Cairns, Paul Todd e Tony Parsons. No fim do ano, o baterista Doug Sampson abandonou a banda por motivos de saúde. Em Novembro de 1979, a banda assinou contrato com uma gravadora de renome, a EMI, uma parceria que se mantem até aos dias de hoje. Poucos antes de entrar em estúdio, Parsons foi substituído pelo guitarrista Dennis Stratton, que trouxe Clive Burr, um amigo seu, para a bateria. Inicialmente a banda queria contratar o melhor amigo de Dave Murray, Adrian Smith, mas Smith estava ocupado tocando guitarra e cantando com sua banda Urchin.