A primeira apresentaçao da banda aconteceu em Londres, na East End , no primeiro de maio do ano de 1976. Depois disso, a banda continuou a fazer apresentações no Cart and Horses Pub em Stratford. A formação original da banda juntava Steve Harris a Paul Day (vocalistas); Dave Sullivan e Terry Rance (guitarristas) e Ron Matthews (baterista). Paul Day mais tade foi substituído por Dennis Wilcock que usava fogo, amquilhagem e sangue falso no palco, ao qual trouxe Dave Murray para a banda, havendo a saída da prieira dupla de guitarristas. Murray permanece na  banda até hoje. Bob Sawyer entrou na banda no final de 1976 como segundo guitarrista, mas como tinha desentendimentos com Murray, fez com que Dennis Wilcock se oposesse a Dave, e então Dennis sugeriu a expulsão deste. Bob não ficou para trás e foi expulso da banda, ois fingia tocar guitarra com os dentes. Ron Matthews aguentou um pouco mais. Havia um guitarrista de outra banda que tocava nos pubs (Terry Wapram) e os Iron Maiden convidaram-no a entrar e Wapram realizou alguns espetáculos como único guitarrista a solo. Dave Murray juntou-se a Adrian Smith na banda Urchin em 1977, enquantos os Iron Maiden passavam um mau bocado: Steve e Dennis chamaram Thunderstick (Barruy Graham) para a bateria e Tony Moore para o teclado, mas após um concerto perceberam que o teclado não seria bom substituto para a segunda guitarra. A banda estava desconconte e o ambiente não ajudava nada. Após alguns ensaios, Moore dicidiu ir-se embora. Nesse momento, Harris foi a um ensaio do Urchin para chamar Murray de volta à banda, o que aconteceu com grande sucesso. Wapram ficou indignado, pois perderia parte das atenções, não aceitou Murray de volta e teve que sair. Com Murray de volta e apenas quatro integrantes na banda, esta decide marcar um espetáculo no Bridgehouse e o outro no pub Green Man. O primeiro foi um fiasco, pois o baterista errou em várias músicas e também gritou para o público calar-se. Nessa altura Wilcock já tinha dito a alguns fãs que iria sair da banda, e o espetáculo estava em volta disso. Foi o que aconteceu. No intervalo entre o  espetáculo de Bridgehouse e o Green Man, Dennis não disse nada e não compareceu no pub. Harris foi à sua casa, mas o vocalista negou-se a cantar uma última vez. De rastos com esta situação toda, Harris voltou para cumprir com o acordo e os Iron Maiden apresentaram-se como um trio em abril de 1978, com Harris, Murray e Thunderstick. Steve expulsou o baterista, já tendo Doung Sampson para ocupar o devido cargo. Com este novo trio, estes passaram meio ano a ensaiar antes de tocar ao vivo ou até mesmo antes de encontrar alguém para entrar na banda.