Lorsque Steve Harris a joint un groupe du nom de Smiler où les membres étaient beaucoup plus vieux que lui. Ils ne voulaient pas qu'un bassiste compose ses propres pièces, alors Steve a décidé de créer son propre groupe. C'est ainsi qu'à la fin de 1975 Iron Maiden a été créé, nom qui est inspiré du vieux film "The Man In The Iron Mask". En 1976, la formation a fait plusieurs spectacles à East End à Londres. Le chanteur original Paul Day a été remplacé par l'ancien chanteur de Smiler, Dennis Wilcock, qui a également recommandé le guitariste Dave Murray. Les guitaristes actuels, Terry Rance et Paul Sullivan, ont pris le tout comme un insulte et ils ont quitté le groupe. Le nouveau a été Bob Sawyer sous le nom Bob D'Angelo.
Bob a tenté de faire une sorte de compétiton avec Dave et il a été renvoyé après six mois. Plus tard, il a joint le groupe Urchin, un groupe de son vieil ami Adrian Smith. Le groupe a décidé temporairement d'abandonner l'idée originale d'avoir deux guitaristes. Nouveaux au sein de la formation, Terry Wapram (guitare) et Tony Moore (clavier). Le batteur Ron Rebel a également quitté le groupe et il a été remplacé par Barry "Thunderstick" Purkis. Le groupe a réalisé que le clavier n'était pas la meilleure idée, alors Moore a été forcé de quitter Iron Maiden, suivit par Wapram qui disait ne pas pouvoir jouer sans clavier.
Il y a plusieurs nouveaux changements dans le groupe mais un chanteur du nom de Paul Di'Anno s'est vu recommandé pour joindre Iron Maiden. À la fin de 1978, Iron Maiden avait une équipe stable et ils ont fait plusieurs spectacles. Ils ont enregistré leurs premières pièces démo: "Prowler", "Invasion", "Strange World" et "Iron Maiden" au Spaceward Studios, ce qui leur a coûté pratiquement tout ce qu'ils avaient. La démo a attiré beaucoup d'attention. John Darnley de EMI a vu le groupe en spectacle et il a décidé de les signer avec la compagnie. Geoff Barton de la revue "Sounds" a évoqué le terme, maintenant devenu célèbre, "The New Wave Of British Heavy Metal" et Iron Maiden était dorénavant sur la route du succès mondial. Après la sortie des deux premeirs albums du groupe, "Iron Maiden" et "Killers", il est devenu clair en 1981 que le chanteur Paul Di'Anno ne pouvait plus demeurer avec le groupe. Il est tombé dans l'alcool et la drogue et, malgré les indications des médecins et du groupe, il a endommagé énormément ses cordes vocales et sa santé en générale. Bruce Dickinson s'est joint à eux, il a quitté son ancien groupe, Samson, qui allait dans la mauvaise voie.
En 1982, ils débutent l'enregistrement du légendaire album "Number Of The Beast". Le succès est venu immédiatement avec le single "Run To The Hills" en Angleterre. Ce succès a également été partagé dans les palmarès européens et américains. Une grande tournée de 180 spectacles a eue lieu pendant huit mois, "Beast On The Road Tour". Par la suite, le batteur Clive Burr quitte le groupe et il est remplacé par Nicko McBrain. La formation a immédiatement débuté le travail pour l'album "Piece Of Mind", qui a été enregistré à Nassau dans les Bahamas. L'album "Powerslave" a été enregistré à Nassau en 1985.
Ils ont fait encore une fois des tournées et le festival Rock In Rio devant 200 000 amateurs. Le spectacle à Long Beach a été utilisé pour le prochain enregistrement de Iron Maiden, "Live After Death", le premier album double live.
"Somewhere In Time" a été mis en vente au mois de Septembre 1986, cette fois-ci enregistré à Nassau et à Munich. Sur ce disque, il y a eu l'ajout d'un clavier, mais rien qui viendrait briser le son classique de Maiden. L'album continue d'être classifié or et platine sur tous les territoires majeurs. L'album "Seventh Son Of A Seventh Son" a été mis en vente en 1988, le premier album concept du groupe. Ce n'était pas l'idée de base, mais il semblait que le disque avait des thèmes reliés. En Janvier 1990, c'est au tour de l'album "No Prayer For The Dying" de voir le jour, mais avant ceci, Adrian a décidé de quitter le groupe. C'était le premier changement depuis plus de 7 ans. Le guitariste Janick Gers s'est joint à eux par la suite. L'enregistrement a eu lieu au studio Barnyard de Steve en Angleterre. Ils été mis en vente le 1er Octobre. L'album
"Fear Of The Dark" a été mis sur le marché en 1992.
En Mars 1993, Bruce annonce qu'il quitte le groupe pour se concentrer sur ses autres projets. Après de nombreuses recherches, ils ont sélectionné Blaze Bayley de Wolfsbane comme nouveau chanteur. Les résultants sont les albums "The X-Factor" en 1995 et "Virtual XI" en 1998. Ce sont les deux albums les plus controversés de Iron Maiden, et les plus décevants pour plusieurs fans, qui n'aimaient pas réellement Bayley au vocal. En Janvier 1999, Blaze Bayley quitte le groupe et le retour de Bruce Dickinson et d'Adrian Smith a donné une nouvelle énergie à Iron Maiden.
Ils ont mis en vente "Brave New World" en 2000, l'album live "Rock In Rio" en 2002, l'album "Dance Of Death" en 2003 et l'album live "Death On The Road". Depuis l'année 2000, ils ont mis sur le marché une grande quantité de DVD, d'albums live et de compilations.