Pagal susikūrimo datą "Iron Maiden" truputį nepasisekė. Jis įvyko tarp dviejų metalinių erų - pirmoji hard rock banga jau buvo nuslūgusi, o antroji (kurioje grupei teko suvaidinti labai svarbų vaidmenį) - dar neprasidėjusi. D.Britanijoje karaliavo punk rock ir ilgaplaukiai vaikinai su gitaromis, grojantys sunkią muziką buvo niekam nereikalingi.
Bosistas Steve Harris įgavo muzikanto patirties Londono grupėse "Gypsy‘s Kiss" ir "Smiler". Grodamas pastarajame kolektyve Steve stengėsi aktyviai dalyvauti ir dainų kūrimo procese, tačiau neretai jo idėjos buvo atmetamos. Kadangi S.Harris rašė vis daugiau ir daugiau, o jo idėjos nelabai tiko tuometinėje jo grupėje, bosistas matė vienintelę išeitį - sukurti savo komandą. 1975 m. naująjį kolektyvą Steve pavadino "Iron Maiden", o pirmojo koncerto, įvykusio 1976 m. gegužę, "meidenų" sudėtis nedaug ką sako šiandien - be Steve Harris, daugiau būsimų žvaigždžių nebuvo - vokalistu buvo Paul Day, būgnininku Ron "Rebel" Matthews, gitaristais Terry Rance ir Dave Sullivan. Už pirmąjį koncertą grupė gavo 5 svarus, o jų pasirodymą stebėjo 8 žiūrovai.

Pirmasis vokalistas turėjo neblogus vokalinius sugebėjimus, tačiau visiškai nemokėjo elgtis scenoje. Netrukus jį pakeitė visiška jo priešingybė - Dennis Willcock, niekam tikęs vokalistas, tačiau puikus šoumenas scenoje. "Meidenų" lyderis pamatęs, jog pora gitaristų visiškai neprogresuoja, tuoj pat juos išprašė lauk, o vietoje jų pasikvietė Dave Murray ir Bob "Angelo" Sawyer. Deja, Murray ir Willcock nelabai sutardavo tarpusavyje, ko pasakoje Dave paliko "IM" ir perbėgo į kitą Londono grupę "Urchin", kurioje buvo kita būsima žvaigždė - Adrian Smith.
Kitas naujokas irgi "meidenuose" neilgai ištvėrė - Sawyer pasuko kitais keliais, o S.Harris pabandė paeksperimentuoti - vietoje gitaristų poros į grupę pasikvietė tik vieną gitaristą Terry Wapram ir klavišininką Tony Moore. Tačiau kokie gi "Iron Maiden" su klavišininku? Eksperimentas nepavyko, o T.Moore paliko kolektyvą. Galiausiai įvyko ir būgnininkų kaita - naujuoju grupės nariu tapo Barry "Thunderstick" Purkis.
Tačiau tokios sudėties "IM" sugrojo... tik viename koncerte. Kuomet grupę paliko vokalistas ir būgnininkas, į "IM" gretas sugrįžo Dave Murray, o naujuoju būgninku tapo Doug Sampson, pažįstamas su "meidenų" lyderiu dar nuo "Smiler" laikų.
Sunkiau sekėsi ieškoti vokalisto. Galiausiai pamaina Willcock buvo rasta. Su dainininko Paul Di‘Anno atėjimu prasidėjo nauja era grupės istorijoje. Maždaug tuomet buvo sukurtas ir grupės talismanas - baidyklė Eddie, iš pradžių kurios tik galva kabėdavo virš būgnininko ir spjaudydavo kraujais arba leisdavo dūmus į sceną. Vėliau Eddie tapo vos ne šeštuoju grupės nariu - dažniausiai grupės vadybininkas, aprengtas Eddie kostiumu išeidavo pašėlti į sceną.
Padažnėjo grupės koncertų, "meidenų" populiarumas po truputį augo ir atsirado poreikis išleisti pirmąjį demo. 1978 m. 200 svarų kainavęs demo įrašas pagaliau buvo įrašytas ir padėjo atkreipti į save ir Londono spaudos dėmesį.
S.Harris pasiskolino iš tetos pinigų ir nutarė išleisti pirmąjį singlą. 1979 m. pradžioje 5000 egzempliorių tiražu buvo išleistas pirmasis "IM" kokybiškas įrašas "The Soundhouse Tapes". Buvo numatyta įrašyti 4 kompozicijas, tačiau užteko pinigų vos trejoms. Singlas buvo greitai išpirktas. Tuomet grupė susipažino su vadybininku Ron Smallwood, kuris sutiko laikinai pasirūpinti "meidenų" reikalais, tačiau gavosi taip, jog jo bendradarbiavimas su "IM" tęsiasi iki šių dienų. Susiradę stiprų vadybininką, muzikantai metė savo turimus darbus ir visu 100 procentų nutarė atsiduoti muzikai.
S.Harris tuomet nutarė, kad grupei reikalingas dar vienas gitaristas. Naujoku tapo Paul Todd, kuris spėjo tik nusifotografuoti vienoje fotosesijoje ir "meidenus" paliko. Jį pakeitė Tony Parsons, tačiau šis irgi neužsibuvo. Sudėtis nusistovėjo atėjus Dennis Stratton, o prie būgnų sėdus Clive Burr.
Vadybininkas R.Smallwood į vieną koncertą pakvietė įrašų kompanijos EMI atstovus, tačiau prieš koncertą įvyko nemalonus incidentas, kai dėl peilio nešiojimosi su policininkais susitumdė Paul Di‘Anno, kuris trumpam buvo nuvežtas į areštinę. Koncertą "IM" pradėjo be vokalisto... kadangi daugelio dainų autoriumi buvo S.Harris, jis vienintelis be Di‘Anno mokėjo dainų žodžius. Nors Harris buvo gan silpnas vokalistas, vis tiek publika šėlo. O likus pusvalandžiui, į sceną užlipo ir pats Di‘Anno. Nepaisant nuotykių, EMI atstovams "meidenai" paliko labai gerą įspūdį ir to pasakoje buvo nutarta porą "IM" kūrinių patalpinti į legendinį rinkinį "Metal For Muthas".
Grupės kaina vis augo, tad nutarta į rinką išmesti dar vieną singlą "Running Free", o muzikantams pavyko "specialių svečių" teisėmis keliuose koncertuose dalintis viena scena su legendiniais "Judas Priest". Debiutinis albumas "Iron Maiden", išleistas 1980 m. balandį iškėlė "meidenus" į naujosios metalo bangos (New Wave of British heavy Metal) lyderius.
Kalbos apie naują britų grupę pasklido ir už Atlanto, tad amerikiečiai "KISS" iškart pasikvietė kartu surengti žiemos koncertus. Viskas klostėsi neblogai, kol neprasidėjo problemos su gitaristu D.Stratton, kuris norėjo groti lengvesnę muziką. Tuomet kitas gitaristas D.Murray prisiminė savo seną draugą Adrian Smith, kuris su D.Murray sudarė vieną įspūdingiausių gitaristų duetų.
1981 m. buvo išleistas antrasis albumas "Killers", kuris buvo įvertintas šiek tiek prasčiau nei debiutinis albumas, tačiau vis tiek gerbėjų armija po truputį augo. Rugsėjo mėnesį "IM" gerbėjų laukė nauja staigmena - iš grupės buvo išmestas Paul Di‘Anno. Oficialiai buvo pranešta, jog priverstinė vokalisto išėjimo priežastis - polinkis į alkoholį ir kokainą. Pats Di‘Anno vėliau leptelėjo, jog tuo metu jis ne vienintelis grupėje turėjo tokių problemų.
Naujuoju "meidenų" frontmenu tapo kitos NWOBHM grupės "Samson" vokalistas Bruce Dickinson. Su juo 1982 m. buvo įrašytas vienas geriausių albumo roko istorijoje - "The Number of the Beast". Po to grupė patraukė į pasaulinį turą, kuris susidėjo iš 150 koncertų. Pirmieji tikros šlovės metai baigėsi.
1983 m. prasidėjo su eilinėmis problemomis su sudėtimi. Išlindo yla iš maišo - Paul Di‘Anno buvo teisus, kad su svaigalais piktnaudžiavo ne jis vienas - būgnininkas Clive Burr taip pat dėl šios priežasties atsisveikino su grupe. Jam pamaina buvo rasta prancūzų grupėje "Trust" - paskutiniuoju legendinės sudėties "IM" nariu tapo Nicko McBrain. Tiesa, prancūzai "Trust" į tuščią būgnininko vietą priėmė... Clive Burr.
Atsinaujinusi grupė iškart užsidarė įrašų studijoje, kur įrašinėjo albumą "Piece of Mind", po kurio išleidimo vėl "meidenai" pasileido į gastroles, trukusias 7 mėnesius. Vokietijoje, Dortmundo mieste vykusiame koncerte "buvo nužudytas" Eddie. Visą šou filmavo televizija, tačiau pabijojo "egzekuciją" parodyti žiūrovams dėl neva per žiaurių smurto scenų.
Taigi, nors Eddie ir buvo "nužudytas", jau sekančio albumo ("Powerslave", 1984) viršelyje jį matome mumifikuotą. "Powerslave" įsimintinas tuo, kad vėl "meidenai" parodė savo aukštą klasę muzikine prasme, ir tai buvo pirmasis albumas, įrašytas ta pačia sudėtimi, kaip ir ankstesnis darbas.
"IM" išvyko į pasaulinį turą, kuris tęsėsi beveik metu. Jo metu JAV įrašyti koncertai buvo išleisti dvigubu koncertiniu albumu "Life After Death" ir vaizdo juostose.
Po varginančio turo, grupė pritilo ir sugrįžo tik 1986 m. su albumu "Somewhere in Time". Grupė fanus šokiravo su nauju skambesiu - muzikoje pradėti naudoti gitariniai sintezatoriai (tais pačiais metais "Judas Priest" tokiu pat principu išleido prieštaringai vertinama albumą "Turbo"). Ne visiems "meidenų" fanams patiko tokie eksperimentai, tačiau sėkmingiausiai singlas "Wasted Years" ir vėl susilaukė visuotinio pripažinimo.
1988 m. išleistas naujas albumas "Seventh Son of a Seventh Son" išsiskyrė tuo, kad tai buvo konceptualus darbas. Nepaisant gerų kritikų įvertinimų, visgi vėl buvo prikišama grupei, kad jos muzika per daug apkrauta gitariniais sintezatoriais. Tačiau tais pačiais metais Doningtone įvykusiame liūdnai pagarsėjusiame "Mosters of Rock" festivalyje "meidenai" buvo pakviesti kaip "headlaineriai". O festivalio dalyvių sąrašas buvo įspūdingas - "Kiss", David Lee Roth, "Guns N‘Roses", "Megadeth" ir "Helloween".
Po to vėl "IM" stovykloje pasidarė tylu, kol galiausiai buvo pranešta apie Adrian Smith išėjimą iš grupės, kuris panoro tęsti solo karjerą. Kiek nerimo suteikė ir B.Dickinson, išleidęs savo solinį albumą. Nors sklido kalbos apie tai, jog "Helloween" vokalistas Michael Kiske taps naujuoju "meidenų" frontmenu, Dickinson pareiškė, jog nepalieka grupės. Netgi priešingai, iš savo solo projekto, Bruce pasikviečia į "meidenus" lenkų kilmės gitaristą Janick Gers,  muzikos pasaulyje žinomą kaip ištikimą Ian Gillan solo projekto bendražygį.
Nauja sudėtimi 1990 m. buvo išleistas diskas "No Prayer For the Dying". Albumas buvo perkamas neblogai, vėl buvo daug koncertuota, tačiau pamažu susidomėjimas sunkiuoju metalu pasaulyje slūgo.
1992 m. naujas albumas "Fear of the Dark" išsiskyrė tuo, kad pirmąkart jam viršelį nupiešė ne "etatinis meidenų dailininkas" Derek Riggs, o įspūdingą "medinuką" sukūrė Melvyn Grant. Britanijos perkamiausių albumų sąraše naujasis "meidenų" darbas iškart debiutavo pirmoje vietoje tačiau kritikos būta ir nemažai. Pasaulyje jau karaliavo grunge muzika, tad nors "Iron Maiden" antrą kartą grupės istorijoje buvo pakviesti kaip didžiausios žvaigždės "Monsters of Rock" festivalyje Doningtone, tačiau reikalai nebuvo jau tokie geri. Vokalistas Bruce Dickinson šįkart labai rimtai užsidegė noru pradėti solo karjerą. Paskutinis koncertas su juo įvyko "Pinewood Studios" salėje, kur buvo įleisti tik grupės fan klubo nariai. Įspūdingą šou surengė magas Simon Drake, koncerto pabaigoje įspūdingai "nužudęs" "meidenų" frontmeną. Vėliau šis pasirodymas buvo įamžintas videofilme "Raising Hell". B.Dickinson erą 1993 m. pabaigė virtinė koncertinių albumų - "A Real Live One" (į kurį įėjo paskutiniojo turo su B.Dickinson įrašai iš 1986-1992 m. kūrybos), "A Real Dead One" (paskutiniojo turo su B.Dickinson įrašai iš 1980-1984 m. "meidenų" eros), "Live At Donington (grupės pasirodymas legendiniame "Monsters of Rock" festivalyje).
Po to prasidėjo naujojo vokalisto paieškos. Nors pretendentų buvo tūkstančiai, netgi buvo kalbama, kad į grupę bus priimtas Bruce pirmtakas Paul Di‘Anno, tačiau kiek netikėtai buvo pasirinktas "Wolfsbane" vokalistas Blaze Bayley. Su juo buvo planuojamas sugrįžimas 1994 m., tačiau grupės naujokui patekus į motociklo avariją, "meidenai" koncertus ir naują albumą atidėjo iki 1995 m.
Naujasis "Iron Maiden" dainininkas savo balsu ir maniera labai skyrėsi nuo B.Dickinson, todėl naujasis albumas "The X Factor" susilaukė labai kontroversiškų vertinimų. Viena vertus, grupės pagrindinis kompozitorius Steve Harris vėl sužibėjo, pateikdamas gerbėjams tamsų ir niūrų albumą, tačiau be B.Dickinson "meidenai" jau buvo ne tie...
"Iron Maiden" pradėjo gastroles Izraelyje, po to sekė koncertai Rytų Europoje, tačiau turas buvo gerokai sutrumpintas dėl Blaze Bayley alergijos įvairioms medžiagoms, naudojamoms scenoje.
1996 m. buvo išleistas pirmas oficialus rinktinis albumas "Best of the Beast", kuriam buvo sukurta nauja daina "Virus" ir įrašytas ankščiau neskelbta puiki koncertinė "Afraid to Shoot Strangers" versija (galbūt geriausias įrašas Blaze Bayley karjeroje). 
Sekančiais metais Steve Harris įkūrė savo nuosavą įrašų studiją Beast Records ir pradėjo dirbti prie naujojo albumo. 1998 m. pradžioje pasirodė naujasis "Iron Maiden" darbas "Virtual XI". Nors jame buvo vienas iš sėkmingiausių pastarųjų metų singlų "Futureal", tačiau pats albumas komerciniu požiūriu tapo pačiu nesėkmingiausiu nuo "Killers" laikų. Nebeatlaikęs įtampos ir spaudimo, Blaze Bayley paliko grupę, o į jo vietą sugrįžo "žmogus-sirena" - Bruce Dickinson. Negana to, į grupę sugrįžo ir gitaristas Adrian Smith. Taip "meidenai" tapo sekstetu.
Legendinės sudėties sugrįžimui pažymėti buvo išleistas rinktinis albumas "Ed Hunter", kur internetu fanai balsavo už kūrinius, kuriuos norėtų rasti diske. Naujas materialas buvo paruoštas 2000 m. ir vadinosi "Brave New World". Po sėkmingą darbą išleidimo sekė anšlaginiai koncertai kartu su "Judas Priest" lyderiu Rob Halford ir amerikiečiais "Queensryche".
2002 m. grupė sudalyvavo "Rock In Rio" festivalyje, kur pasirodymas kitais metais buvo išleistas tiek cd, tiek dvd pavidalu. Tais pačiais metais buvo išleistas kiek kontraversiškas albumas "Dance of Death". Vieni jį dievino, kiti įžvelgė didelę krizę Steve Harris kūrybiniame ir asmeniniame gyvenime (S.Harris tuomet tvarkėsi skyrybų dokumentus).
Po albumo išleidimo vėl sekė didelis turas, kur buvo koncertuota 28 šalyse 1,5 milijono žiūrovams. Vienas koncertas Dortmunde buvo nufilmuotas ir vėl išleistas tiek koncertinio audio disko, tiek dvd formate ir vadinosi "Death on the Road".
2006 m. "Iron Maiden" vėl sukėlė didelį šurmulį išleisdami naują albumą "A Matter of Life and Death". Šiemet grupė vėl nustebino milijonus savo fanų - buvo sukurtas filmas "Flight 666", kuriame rodomas grupės narių gyvenimas pasaulinio turo metu. Deja, Pabaltijo šalyse tik Rygos kino teatras įtraukė šį filmą į savo repertuarą. Ateinančiais metais "meidenai" žada sugrįžti su visiškai nauju albumu ir nė kiek neketina mažinti apsukų.