Název kapely údajně vznikl podle filmu Muž se železnou maskou, který v té době běžel v televizi. Poté, co skupina odehrála několika hospodských koncertů, odešel z ní zpěvák Paul Day, kterého nahradil Dennis Wilcock. Problémy začínali být také s kytaristy, kteří neuměli hrát pro metalovou hudbu tolik důležitá sóla. Tento problém sice částečně vyřešil Wilcockův kamarád Dave Murray, který začala s kapelou úzce spolupracovat, avšak oba dosavadní kytaristé stejně skupinu museli opustit. Součástí sestavy se v roce 1980 stal kytarista Adrian Smith. Skupina v průběhu své kariéry prošla ještě velkým množstvím personálních změn. V současnosti jsou členy hudební formace zpěvák Bruce Dickinson, baskytarista Steve Harris, kytarista Dave Murray, kytarista Adrian Smith, kytarista Janick Gers a bubeník Nicko McBrain.
Kapela se proslavila nejen díky své hudbě, ale také díky svému maskotovi Eddiemu, který se objevuje na obalech všech alb a singlů kapely – výjimkou je jejich debutový singl s názvem Running Free. K roku 2010 skupina prodala více než 85 milionů alb a obdržela jednu cenu Grammy. Na kontě má také mnoho dalších cen – mezi nimi cenu Ivora Novella, Juno nebo BRIT Awards.
Do roku 2010 skupina vydala celkem patnáct studiových alb, na kterých v různých obdobích zpívali tři zpěváci − Paul Di'Anno, Bruce Dickinson a Blaze Bayley. Jediným stálým členem skupiny zůstal Harris, na všech albech se však podílel i kytarista Dave Murray.