Au milieu des année 75, un jeune nommé Steve Harris eut l'idée de former un groupe de Rock dur (Heavy Metal) qui s'appellerai Iron Maiden . Le nom Iron Maiden est inspiré d'un film appelé "L'homme au masque de fer " . Iron Maiden peut avoir un double sens, d'une part ça peut être un instrument de torture médiéval (Un cercueil tapissé a l'intérieur de pointe aiguë), d'autre part, c'était le surnom de la première ministre Margaret Thatcher, ce qui provoqua une grande polémique en Angleterre, surtout sur les couvertures des premiers albums.

(Je vais passer la période 75-79 car elle a peut d'intérêt, mais si vous tenez absolument a connaître cette période, je la rajouterai peut-être)

Fin 78, Harris, Murray, Di Anno et Samson (Batteur de l'époque), préparèrent un disque, et le 30 décembre ils allèrent au Studios Cambridge's Spaceward et enregistrèrent Strange World, Iron Maiden, Invasion, et Prowler. En 1979 apparaît Rob Smallwood, il écoute l'enregistrement en avril 79, et Harris lui téléphone pour qu'il aille les voir jouer en direct (Maiden faisait la tournée des grands bars de Londres), mais au premier rendez-vous les Maiden eurent une forte discussion avec le propriétaire de Pub et finalement, ils ne jouèrent pas. Pourtant cela n'empêchas pas la rencontre entre les Maiden et Rod Smallwood, qui occasionna un deuxième rendez-vous mouvementé aussi, car le jour même du concert, Paul Di Anno fut arrêté par la police pour port d'arme blanche. Ce qui fit que les Maiden jouèrent pour la première fois en trio, avec Steve comme chanteur. Pour Rod Smallwood ce n'était pas un gros problème de ne pas avoir de chanteur, il devint immédiatement leur manager et centra tous ses efforts sur ce groupe qu'il considéra dans un premier temps comme une perle rare.