Historien om Iron Maiden starter i 1971, da 15 år gamle Steve Harris, inspirert av Wishbone Ash, Jethro Tull og tidlig Genesis kjøpte en Telecaster bass for 40 pund. Steve hadde tidligere et stort ønske om å en dag spille fotball for sin elskede klubb West Ham, og hadde faktisk signert en lærlinge kontrakt med dem. Men mengden talenter på lærlingekontrakt for West Ham på disse tider var stor, og antallet som greide seg helt frem til profesjonell fotball spiller var få. Samtidig førte all treningen og kampene til at unge Harris ikke kunne bruke så mye tid sammen med venner, han hadde ikke tid til å gå på konserter, drikke og sjekke damer sammen med dem. Etter å ha tenkt hard og lenge, ga han opp håpet på en fotball karriere og satset istede på å lære seg mest mulig om rock musikk. Han lærte seg spille ved og høre på sine favoritt plater å samtidig spille med, pluss at han spilte med venner. Dette førte til at de startet bandet Influence, som etter hvert skiftet navn til Gypsy's Kiss.

The Gypsies fikk sin deby på en talent konkurranse i Poplar, spilte seks konserter før ga seg. Steve som var full av ambisjoner, begynte så i et band som kalte seg Smiler. De andre band medlemmene var flere år gamlere en ham, selv om han fikk verdifull erfaring følte han seg "kvalt". Smiler var et "good time boogie" band som selv om de spilte en tidlig versjon av "Innocent Exile", godtok de ikke andre sanger skrevet av Steve. De gjorde det klart at de ikke ville at deres bass spiller skulle springe rundt og skrive sanger. Tilslutt fant Steve ut at hvis han skulle få det som han ville måtte han danne sitt eget band, og i slutten av 1975 ble Iron Maiden født. Steve fant på navnet etter å ha sett en "Iron maiden" i en gammel verson av filmen "The man in the iron mask". Det var en metall kiste med spisse nagler på innsiden, hvor ofrene ble plassert og torturert til døde.

Våren 1976 sikret bandet seg faste spille jobber på The Cart and Horses pub i Stratford i London's East End. De første spillejobbene gikk sånn passe, men Steve følte fortsatt at det var noe som manglet. Vokalist Paul Day ble erstattet med eks-Smiler vokalist Dennis Wilcock, og han anbefalte en talentfull ung gitarist med navnet Dave Murray. Dette tok de bandets gitarister Terry Rance og Paul Sullivan som en fornærmelse og forlot bandet. Bob Sawyer, som brukte navnet Bob D'Angelo, ble rekruttert som ny andre gitarist, og med Ron Rebel som trommeslager ble det den første Iron Maiden "line-up". Etterhvert begynte bandet og få spillejobber over hele East London, og bygde opp en sterk lokal tilhengerskare. Etter seks måneder ble "line up'en" endret igjen, Bob måtte gå. I stede for å utfylle Dave's gitar, prøvde han istede å konkurrere med ham. Så, etter en krangel på The Bridgehouse, ble Dave sparket av Dennis. Han ble etter dem med i bandet Urchin, som var bandet til hans gamle venn Adrian Smith.

Etter alt bråket, bandet bestemte seg for midlertidig å gå bort fra konseptet med to gitarer. Terry Wapram sluttet seg til bandet som gitarist samt at Tony Moore ble rekruttert som keybordist. Ron Rebel kunne heller ikke takle dette bråket. Han ble erstattet av Barry Purkis, som senere kalte seg selv Thunderstick. Etter en spillejobb på The Bridgehouse ble de smertelig klar over at keyboard ikke var noen løsning, så ut med Moore. Da mente Wrapham at han ikke kunne spille uten at det var noe keyboard med, så han sluttet også. Da dro Steve på en Urchin konsert og overtalte Dave til og komme tilbake til Maiden. Dennis sluttet like før en spillejobb i South London, og da Thunderstick også dro så alt mørkt ut. Steve rekruterte så eks-Smiler trommeslager Doug Sampson, så samtidig som denne nåværende trioen øvde så de seg om etter en ny vokalist. Tilslutt anbefalte en venn av Steve en mann med navnet Paul Di'Anno. Paul besto auditionen med glans, og bandet kunne se fram til et comeback. Men det var vanskelige tider, da Punk/new wave bølgen var på topp i 1977 og omtrent alle steder ble bare New wave band tatt inn. Det samme med plateselskapene. De mottok tilbud, men bare hvis de ville klippe håret og spille punk. Unødvendig å si hva Steve svarte!

Situasjonen forbedret seg mot slutten av 1978, og de fikk sitt comeback og regelmessige spillejobber. De skjønte at de trenget en demo, så nyttårsaften stilte de i Spaceward Studios nær Cambridge og spilte inn "Prowler", "Invasion", "Strange world" og "Iron Maiden. De 200 pundene de hadde dekket kun innspillingen, så de hadde ikke råd til og kjøpe mastertapen. Da de dro tilbake noen uker senere for å betale for den, hadde den blitt slettet. Alt som var igjen var fra innspillingen var de uredigerte og umixete kassettene. Dave gå sin kopi til Neal Kay, en DJ med en lidenskapelig kjærlighet for hard rock og holdt faste rocke show på The soundhouse, en tilstøtende klubb til Bandwagon pub i Kingsbury, North London. Det ble nå lettere for bandet å få spillejobber, og gjorde seg fortjent til mer faste jobber på The Ruskin Arms på Minor Park. Neal spilte kassetten på en av sine "Soundhouse Nights" og ble overrasket av reaksjonene, det ble den mest etterspurte musikken der for flere måneder og endte med at Maiden begynte og spille der. Dette hadde også kommet Rod Smallwood for øret, som gjennom en felles venn av ham og Steve fikk kassetten. Etter og å hørt kassetten og sjekket ut bandet, tilbød han seg og være manager for bandet. Rod arragerte spillejobber over hele landet, som førte til at bandet fikk bygd opp en nasjonal tilhengerskare. Det ble også arrangert konserter i Central London for å få plateselskapene til å sjekke ut Iron Maiden. På en av disse konsertene, nærmere bestemt 13. oktober, på The Marquee kom John Darnley fra EMI for og se dem. Rod inngikk et veddemål med Marquee's eier om at konserten ville være utsolgt (700 fans) innen kl 19 den kvelden. Rod vant veddemålet og EMI inngikk kontrakt med Iron Maiden den påfølgende måneden. Den sommeren hadde også Maiden blitt omtalt i musikkbladet "Sounds". Det var i det numret at Geoff Barton, som senere startet bladet "Kerrang!", skrev om bandet "The new wave of british heavy metal". Maiden fikk også sin debut på The Music Machine i Camden som "special guests" hos Motorhead, som da spilte under navnet "Iron fist and the hordes from hell". Før året var omme skulle få bandet spille der to ganger til, nå som hovedattraksjon.

I mellomtiden hadde bandet blitt oversvømt med ønsker fra fans som ville ha kopi av demo'en, så de bestemte seg for å gi det ut på sitt eget Rock Hard label. 7" EP'en ble døpt "The Soundhous Tapes", og ble forbeholdt kun for "hardecore" fans og ble bare solgt på konserter og gjennom bestilling via post. De 6000 kopiene ble solgt ut nesten med en gang, som førte til den med en gang ble samleobjekt. Til tross for et stort press fra de store platekjedene etter plata, bestemte bandet seg for at den skulle være noe spesielt for deres fans. Innimellom konsert spillingen, dro bandet til EMI's Manchester Square studio og spilte inn "Sanctuary" og "Wrathchild" å fullføre en LP kalt "Metal for Muthas". De spilte også inn fire sanger for Radio One's "The Friday Rock Show". Gitarist Tony Parsons kom inn som andre gitarist, så det ble et fem manns band igjen.

I august ble bandet invitert av de amerikanske mega stjernene Kiss, til og være supportband for dem på deres europa turnè. Pluss til og spille på Reading på Saturday night som "special guests" til UFO, det ga Steve muligheten til og stå på samme scene som UFO's Pete Way, en av hans store forbilder. Med Kiss gikk alt bra og Maiden's tilhengerskare på kontinentet vokste med en gang. De ble ikke med på konsertene i UK, da de nettopp hadde avsluttet sin egen UK turnè, så tok en uke fri og dro til Italia. Da turnèn med Kiss var avsluttet ble det annonsert at pga "musikalske uoverbestemmelser" Dennis sluttet i bandet. Dennis sin musikksmak var ganske annerledes en resten av bandet, hans ideer var ikke de samme med henhold til hvilke musikalske veier skulle ta framover så en avskjed var nødvendig. Splittelsen skapte bitterhet, men nå er Dennis og bandet gode venner og Dennis driver nå The cart an Horses. Bandet behøvde ikke å se langt etter en erstatter, og Adrian Smith kom inn. Bandet spurte egentlig Adrian før Dennis kom inn også, men fordi det så ut som Urchin skulle bli noe, bestemte han seg for og se det ann. En mini-UK turnè ble kjapt arrangert for å gjøre Adrian kjent. De begynte og jobbe med et nytt album med Martin Birch som produsent. De avbrøt innspillingen en periode for og spille en spesiell jule konsert på London's Rainbow Theater, som ble filmet for en fremtidig video utgivelse. Publikum fikk en tidlig julegave da andre halvdel av konserten måtte spilles på nytt pga problemer med lysinnspillingen. Ingen gikk tidlig!

Februar 1981 kom albumet "Killers"ut, og bandet la ut på sin første verden turnè. Albumet gikk rett inn på 12. plass på UK albumlisten, og ga bandet mange "gull plater" fra mange store markeder. Som i Europa, hadde "Killer " World Tour sine først besøk i Canada, USA og Japan. En live EP med sanger spilt inn i Japan ble utgitt med navnet "Maiden Japan". I mars kom en 30 minutters video fra Radio Christmas shoe ut. Da slutten på "Killer" world tour nærmet seg slutten ble det klart at Paul Di'Anno's dager var talte. Han hadde levd ut myten om en rocke livsstil til fulle, selv om han ble advart både fra resten av bandet, Rod og doktorer. Han begynte også å gå bort fra Iron Maiden stilen, og helte mer mot en mer bluesete stil, en Whitesnake lignende stil. Nok engang var en erstatter i nærheten. Bruce Bruce fra rocke bandet Samson var gått lei av at bandet drev lenger mot den musikken ironisk nok Paul også gjorde. Så Bruce gikk gjennom audition for Maiden, og tok sitt normale navn Dickinson igjen. Ett par hastige oppsatte konserter i Italia introduserte Bruce som vokalist, og han gjorde en triumferende debut i UK på The Rainbow. Bandet benyttet også muligheten og spilte noen sanger som nettopp hadde blitt innspilt til det nye albumet. Bruce ble døpt "the air-raid siren" av fansen pga sin kraftfulle stemme. Året endte med at Maiden returnerte til The ruskin Arms som sitt alter ego Genghis Khan for å spille en kombinert veldedighet/fødselsdag konsert for Dave Murray. Hvis 1981 kunne ses på som et suksess år for Maiden, overgikk 1982 alle forventninger. Bandet var allerede opptatt med en utsolgt britisk del av "The beast on the road", da deres første singel fra deres nye album, "run to the hills" nådde 7. plass på singel lista i UK. Det nye albumet "The number of the beast" blåste all konkurranse av veien med å entre UK lista som nr 1, og inn på topp 10 over hele europa. Den kom også inn på listene i USA og Canada."The beast on the road" levde opp til sitt navn, da de spilte 180 dager på 8 måneder. Nok en gang bandet brøt ny grunn ved å besøke Australia og New Zealand for første gang 29.juni, de spilte sin første konsert i USA på New York's Palladium for fullt hus. I august avsluttet de USA turnèen og fløy tilbake til UK for og spille på The Reading festival foran 35.000 fans. På slutten av turnèen, ble Clive Burr nytt tap i Maiden "line-upen". Personlige problemer og den stramme timeplanen til Iron Maiden krevde sine ofre, så i januar 1983 fløy bandet til Nassau for og spille inn neste plate med en viss Nicko McBrain bak trommesettet. Bandet hadde mott Nicko under UK delen av "Killer" turnèen mens han spilte for det franske bandet Trust, som hadde vært oppvarmingsband for Maiden. I USA ble bandet sammenlignet med satanister av en liten gjeng feilinformerte, påståelige personer som totalt hadde missforstått poenget. Deres påstander, totalt usanne, ga mer publisitet for bandet.

Trommeslager Nico fikk sin ilddåp under innspillingen av "Piece Of Mind" i Nassau. Bandet tok seg fri til og filme inn en promo video for den kommende singelen "Flight of Icarus", manuset trengte noen til og ta på seg blå make-up og ikle seg munke kappe. Nicko som var den nye mannen meldte seg frivillig for rollen. I mai kom det nye albumet ut, og det gikk inn på 3. plass på UK lista og bandet startet sin "World Piece Tour" i Hull City Hall. Turnèen var utsolgt nesten overalt. Som avslutning på turnèen spilte de for et bredt europeisk tv publikum, som en avslutning på konserten gikk bandet til et onskapsfult angrep på deres maskot "Eddie". Tilsynelatende hadde de hatt tanker om og kvitte seg med monster maskoten, men heldigvis var ryktene om Eddie's død betraktelig overdrevet og han var tilbake på albumcover og scener det påfølgende år. Bandet dro så til New York, med en stabil "line-up", til det som så ut som deres travleste år så langt.

1984 startet med et selvsikkert, men ikke selvtilfreds, Iron Maiden som startet med en tre uker pause før de startet arbeidet med det nye albumet. Det var innøvd i Jersey og nok engang innspilt i Nassau. På den tiden "Powerslave" kom ut i September, var bandet allerede tre uker inn den svært anstrengende "World Slayer Tour" og presset grensen til det ytterste. De startet turnèen i Polen, det var første gang at et stort rockeband hadde spilt der med full vestlig produksjon. Bandet spilte også i Ungarn og Jugoslavia, Og den nyskapende "Iron Maiden Behind The Iron Curtain" turnèen var en stor suksse og ga fortjent omtale i verdens medier. På denne tiden var jernteppet fortsatt på plass, og en turnè i disse landene var en stor oppgave. Fra øst-europa retunerte bandet via Italia til UK, hvor "Powerslave" albumet ble sluppet og gikk rett inn som nr.2. Albumet presenterte de mest detaljerte illusjonene så langt, noe det massive sceneshowet viste. Maidens spilte fire netter på Hammersmith Odeon, inkludert veldedighetskonsert med parodi bandet Bad News. Eddie var nå et 6 meter høy monster som dukket opp på slutten av sangen "Iron Maiden". Turnèen var en stor suksess, bandet var på topp, scene showet var imponerende og suvenir salget slo alle rekorder. Bandet avbrøt USA delen av turnèen og gjorde sitt første besøk i Sør-Amerika når de spilte for ca. 200 000 mennesker på "Rock in Rio" festivalen. Høydepunktet på USA turnèen var på Long Beach Arena i Sør California når Iron Maiden, som det første bandet, solgte alle billettene fire netter på rad, til sammen 52.000 billetter. Konsertene på Long Beach Arena ble filmet med et mål om å gi ut enda en live video og live album, med bandet på sitt aller beste. En slitsom ble avsluttet i juli 1985. Live albumet og videoen, begge kalt "Live After Death", kom ut i oktober. Albumet kom opp på andre plass på lista, og videoen var på mest solgte lista i måneder.

Det nye albumet "Somewhere in Time" ble innspilt i Nassau og Munchen, og ble utgitt september 1986. Den kom inn som nr.3 på UK lista og gikk til gull og platinium i alle store marked. For å promotere albumet, dro bandet ut på turnèen "Somewhere On Tour". Det nye albumet viste et markert forandring i bandet's stil, med synthesizer som bakgrunn på mange låter. Men enhver fans som fryktet det skulle "vanne ut" Maiden's stil, trengte bare og på sanger som "Heaven Can Wait" eller "Alexander The Great". Turnèen startet nok engang "bak jernteppet", begynte i Beograd og avsluttet 8 måneder senere i Osaka. Scene showet var nok engang spektakulært, Eddie var nå skiftet til en "cyborg" og klimakset på showet var da hele bandet ble løftet opp i lufta mens en gigantisk oppblåsbart Eddie hode og klør kom fram. Bandet ble også filmet og intervjuet for en dokumentar, som ble sluppet i 1987 og hadde tittelen "Twelve Wasted Years". En kronologisk video om deres vei mot toppen, den inneholdt tidligere uviste arkiv opptak og intervjuer med nøkkel personer i Iron Maiden suksessen. Med en suksess full turnè avsluttet var det på tid og tenke på neste album.

"Seventh son of a seventh son" var et episk mesterverk av et album, det var det første og så langt det eneste "konstept" albumet Iron Maiden har spilt inn. Dette var egentlig ikke ideen, men ettersom de skrev og øvde så de at sangene kom inn under samme tema. Layout'en på coveret markerte også et skifte, ble mer dempet enn tidligere. Også "Seventh Tour of a Seventh Tour" brøt med Maiden's tradisjoner, begynte i USA, og var laget for en kombinasjon mellom arena og festival. Høydepunktet på hele turnèen kom i august, da Maiden var hovedattraksjon på den legendariske "Monsters of Rock" festivalen i Donington, på programmet sto også bla. Kiss, David Lee Roth, Megadeath, Guns 'n Roses og Helloween. Det var en av de beste programmene festivalen har hatt, og det ble satt en publikums rekord det året på 102 000. Maiden spilte en gnistrende konsert og scene showet var fantastisk, og endte med et massivt fyrverkeri. Bandet dro så til europa, før de avsluttet turnèen med en serie arena konserter på hjemmebane. De to konsertene på Birmingham NEC, kanskje de beste "ikke-festival" showene av turnèen, ble filmet for en ny live video som ble redigert av Steve Harris. 12. desember ble den siste konserten spilt på Hammersmith Odeon, en scene med mange tidligere Maiden triumfer. Uten noen planer for noe nytt album i 1989, tok bandet en real pause for å lade batteriene og være sammen med familiene.

Bruce og Adrian brukte pausen på å spille inn solo albumer, mens Steve brukte mesteparten av tiden på å redigere Birmingham opptakene. Bandet kom sammen igjen i november 1989 for slippet av videoen "Maiden England". EMI og Sanctuary hold et overdådig "release"party, med et gjennomgående britisk tema. Rommet var dekorert med Union Jacks, verdens pressen fikk "fish and chips" å spise og øl til drikke, mens bandet brukte tiden på intervjuer og på å bli fotografert. "Maiden England" ble nok engang en bestselger blant musikkvideoer.

I Januar 1990 samlet bandet seg hos Steve for å starte arbeidet med "No Prayer For The Dying". Arbeidet hadde knapt startet før det skulle bli ett nytt personell skifte. Adrian som nettopp hadde gitt ut solo album overrasket med å kunngjøre at han ikke var sikker på at han kunne gi 100% for Maiden, som etter en gjensidig enighet forlot bandet. Heldigvis var erstatteren nok en gang lett å finne. Janick Gers som var velkjent for bandet etter å ha spilt i bandet Gillian, og hadde nylig arbeidet med Bruce på hans solo album og turnè, ble invitert etter en audition. Innspillingen av albumet fortsatte etter planen. For første gang siden "The Number of the Beast" ble albumet spilt inn på britisk jord, i Steve's eget studio, en omgjort låve ved huset hans i Essex. Innholdet på albumet ble mer seriøst, da bandets tekster begynte å omhandle temaer som var aktuelle i tiden. Albumet ble sluppet 1. oktober 1990 og debuterte som nr. 2 på UK listen. Etter at de ikke hadde vært inne på listene på nesten to år, var bandet ivrige etter og komme seg ut igjen og spille live. Turnèen "No prayer on th road" startet med en "hemmelig" konsert i Milton Keynes 19. september 1990. Etter den gigantiske produksjonen på forrige turnè, var det tilbake til en mer normal produksjon med mindre scene sett og mindre lyssetting. Det bare demostrerte at Maiden kunne gi et stort show, uten og behøve å ha mega watt med lyd og lys, og en kostbar produksjon. Janick utgjorde også en stor forskjell live, hans energiske entusiasme og krumspring på scenen, smittet over på alle andre. Bandet og deres fansen satte pris på igjen å være nær hverandre, tilføre hverandres energi og entusiasme, minte om tidligere tider. Turnèen endte i Salt Lake City i mars 1991. Det var egentlig tenkt at turnèen skulle fortsette til Japan og Australia, men vanskelighetene med å reise pga utbruddet av Golf krigen, satte en tidligere avslutting.

Når de igjen begynte og tenke på nytt album, bestemte bandet og managementet at Eddie behøvde en endring. Etter og å ha sett i en skrekk tegneserie ble det bestemt at Eddie skulle være mer rettfram "horror", så tilslutt ble Derek Riggs og flere andre artister invitert til og sende inn forslag til hvordan de så den "nye" Eddie. Et forslag fra Melvyn Grant ble tilslutt valgt. Albumet "Fear of the dark" ble sluppet i mai 1992 samtidig som bandet startet turnèen "Fear of the dark" i Skandinavia. Albumet ga bandet deres tredje nr.1 på UK listen. Iron Maiden ble nok engang spurt om å spille på Donington, i august. Bandet leverte en enda sterkere konsert enn i 1988, de visste hva som var i vente denne gangen og var mindre merket av nerver. Hele konserten ble filmet for en ny live video, som skulle gis ut påfølgende år. Også flere show ble lydinnspilt med tanke på et framtidig live album. Scene var mer kunstferdig utført, men ikke som i `88, og Eddie dukket opp et gigantisk tre skapning, som på album coveret. Turnèen endte 4. november, og mens bandet fløy hjem fra Japan var de uvitende om den store overraskelsen som skulle komme i mars 1993.

Bruce hadde en tid tenkt på å forlate Iron Maiden. Som den arbeidsnarkoman han var, hadde Bruce flere prosjekt gående utenom Maiden og en ung familie, måtte han velge hva han skulle bruke tid på. Noe måtte gis opp, og Bruce følte han hadde nådd dit han kunne med Iron Maiden. Det hadde blitt bestemt at i stede for å utgi et dobbelt live album som gjorde med "Live after death", det nye live opptaket skulle gis ut som to separate album. Det første skulle inneholde matriale fra etter LAD perioden, mens det andre skulle inneholde mer gammelt materiale. Fansen hadde da et valg om å kjøpe begge albumene, eller bare materiale fra hver periode. Samtidig som det første albumet "A real live one" nærmet seg og bandet gjorde seg klar for turnèen "Real live tour", annonserte de etter en erstatter for Bruce. Med det resultat at de ble oversvømt med tusener av kassetter, cd'er og videobånd fra håpefulle. I mellomtiden besøkte de Moskva, og mottakelsen bandet fikk fra russiske "headbangere" var utrolig. Etter at turnèen var ferdig, var det å sette seg ned og komme seg gjennom mengden med demo'er fra vokalister.

Etter en intensiv leting, ble det på slutten av året annonsert at Bruce sin avtaker skulle bli Blaze Bayley, fra bandet Wolfsbane. Wolfsbane hadde spilt som oppvarming under deres turnè i UK i 1990, så bandet hadde hatt muligheten til og se Blaze i aksjon og visste hva han var kapabel til. Blaze var favoritt fra starten av, og etter å ha hørt gjennom demoene og holdt audition'er, var ingen som bandet syntes var mer passende enn han. Etter alt oppstyret med at Blaze ble ny vokalist hadde stilnet, satte bandet i gang med en intensiv øvings periode, slik at Blaze kunne bli kjent med alle. Etter hvert startet de arbeidet med nytt album.

Bandet hadde ikke bare ny vokalist, men også ny produsent. For første gang siden 1980 skulle et Maiden studio album ikke bli produsert eller co-produsert av Martin Birch. Han hadde siden midten på 80-tallet trukket seg halveis tilbake, og bare retunert til mixepulten når Maiden skulle gi ut album, men nå ga han seg helt. Det ble bestemt at Steve skulle dele produsent stolen med Nigel Green. Nigel hadde før vært "tape operator" på albumene "Killers" og "Number of the beast", og hadde senere blitt en topp produsent. Det nye albumet tok over et år og fullføre, og fikk navnet "The X factor". Det kom endelig ut i oktober 1995, mens turnèen "X factour" startet like før.

Turnèen startet med konserter i Israel og Sør-Afrika, dette var første gang bandet var i disse landene, og erfaringene dette gav gjorde at de ville retunere neste gang. Det var også meningen at de skulle spille i Beirut, men de Libanesiske myndighetene trakk tilbake visumene. Selv med lobby virksomhet gjennom diplomatiske kanaler, ble de nektet adgang. Med den uventede pausen dette medførte, fløy bandet tilbake til UK for og være med på MTV's "Most wanted". De fløy så til Romania, og startet sin første omfattende turnè i Øst-Europa(Bulgaria, Slovenia, Ungarn, Polen, Tsjekkia og Romania). Den tvil som kunne være om Blaze sine evner, ble lagt døde da bandet overalt fikk en varm velkomst spesielt hjemme. Konserten på The Brixton var en av de beste gjennom tidene, både bandet og fansen var i "fyr og flamme". Før jul og tidlig på ny året spilte Maiden i vest-europa, før de flyttet over til USA, Canada og Japan. På sommeren spilte de på europeiske festivaler og turnerte i Sør Amerika, som inkluderte "Monsters of Rock" på Sao Paulo stadion hvor de var hoved band foran 50 000 personer.

Tidlig i 1999 forlot Bayley Iron Maiden, og bare noen måneder senere sjokkerte bandet verden da de annonserte gjenforeningen med ikke bare tidligere vokalist Bruce Dickinson, men også tidligere gitarist Adrian Smith. Janick Gers skulle også fortsette i bandet, slik at Iron Maiden nå hadde tre gitarister – noe som er forholdsvis uvanlig for musikalske grupper. I tillegg var det åpenbart at Dickinson valgte å gå tilbake til sine «rene stemme», i stedet for den litt røffere stemmen på No Prayer for the Dying og Fear of the Dark, og alt var plutselig 80-tall igjen. Bandet dro ut på en gjenforeningsturné, og samlet både gamle og nye tilhengere over hele verden.

I 2000 begynte perioden man godt kan kalle «de progressive årene». Bandet slapp albumet Brave New World, basert på Aldous Huxleys roman med samme navn. Låtene var lengre, og tekstene omhandlet alt fra mørke temaer til samfunnskritikk. Bandet fikk en ny tilhengerskare med eksperimenteringen innen progressiv metal, og Brave New World ble sett på som det beste Iron Maiden-albumet på over 10 år.

Verdensturnéen endte i januar 2001 med en konsert på Rock in Rio-festivalen. For bandet, og ikke minst tilhengerne, var det som en drøm gikk i oppfyllelse; Iron Maiden var tilbake der de var på sitt største på 1980-tallet.

Bandet fortsatte med sin progressive trend med albumet Dance of Death (2003). Albumet solgte til platina i flere land, og etterlot seg ingen tvil om at Iron Maiden fremdeles var en heavy metal-sensasjon. Enkelte går så langt som å si at Dance of Death faktisk overgikk Brave New World når det gjelder kreativitet, og at den er det beste albumet siden Seventh Son of a Seventh Son fra 1988. Dance of Death er også det eneste albumet bandet har gitt ut hvor trommeslager Nicko McBrain har bidratt med å lage en låt – «New Frontier» – hvor han skrev basslinjen.

I 2005 annonserte Iron Maiden en turné for å feire at det hadde gått 25 år siden deres første album ble sluppet, og at det hadde gått 30 år siden bandet ble opprettet. En nyutgivelse av Number of the Beast-singelen gikk rett inn som nr. 3 på de britiske hitlistene. Turnéen skulle også støtte opp omkring utgivelsen av DVD-en The Early Days, som er en hyllest til dem selv og musikken de laget i perioden 1976–83.

Høsten 2005 ble CD-en Death on the Road sluppet. Det var i utgangspunktet meningen at denne skulle slippes samtidig med en DVD-utgave, men den lot vente på seg til 6. februar 2006.

28. august 2006 ble "A Matter of Life and Death" sluppet, deres 14. studio album var en realitet. Det var ikke et konsept album, likevel er krig og religion temaer som går igjen så vell i tekstene som cover "artworken". En suksefull turne i Nord Amerika og Europa fulgte, med utsolgte spillesteder som en gjenganger. På denne delen av turneen ble noe så uvanlig hele det nye albumet spilt, i kronologisk rekkefølge samt noen gamle sanger til slutt. Det var under denne turneen Maiden for første gang spilte i Bangalore, India foran ett publikum på 35.000 og ble dermed det første store heavy metal bandet som spilte i landet. De var også hoved band på "The Desert Rock Festival" i Dubai, foran 20.000 publikumere. Under andre del av turneen, sommeren 2007, spilte de på flere store festivaler verden over. Spillelisten ble nå endret for å feire 25 års jubileet for slippet av "The Number of the Beast", hvor de spilte 5 sanger fra "A Matter of Life and Death" og 4 fra "The Number of the Beast". Sommeren ble avsluttet med en konsert på Londons Brixton Academy til støtte for "The CliveBurr MS Trust fund".

5. september 2007 annonsert bandet "Somewhere Back in Time World Tour", samtidig med at en relansering av "Live After Death" skulle komme i 2008. Spillelisten for denne turneen var deres største hit fra 80 tallet, med et spesielt fokus på Powerslave tiden. Turneen startet i Mumbai, India, 1.februar 2008, hvor bandet spilte for et publikum på rundt 30.000. Første del av turneen inneholdt 24 konserter i 21 byer, reiste over 80500 km i et chartret fly med navnet "Ed Force One" og fløyet av Bruce Dickinson. Flyet var også prydet med Iron Maiden og hadde et powerslave tema. Med på flyet av bandet, crewet, famile medlemmer, journalister og alt av utstyr, noe Maiden var det første bandet i verden til og gjøre. De spilte sin første konsert noensinne i Costa Rica og Colombia, og hadde sin første konsert i Australia siden 1992. I forbindelse med denne spesielle og omfattende turneén ble det laget en dokumenter, FLIGHT 666, som viser hvordan det er å være på en verdens omspennnede Iron Maiden turne. Filmen skildrer livet bak scenen, på scenen, på flyet og alt rundt den første delen av turneén i mars og februar 2008. Den hadde premiere på små og store kinoer over hele verden 21. aprill 2009.

Desember 2009 ble nyheten om en turne sluppet, både festival jobber og egne konserter . Start skuddet gikk i USA 9. juni 2010, og fortsatter deretter til Europa og nok engang videre til Australia. På denne turneén ble musikk fra låter fra Brave New Woldt og framover prioritert, til noens forargelse og  andres glede.

16. august ble nok en merkedag dette året, da platen "The Final Frontier" ble sluppet. En plate som fortsatte med trenden med progressiv og tildels episk musikk. I forkant av turnestart ble en låt, Eldorado,fra albumet lagt ut for nedlasting på ironmaiden.com, den ble også endel av setlisten på turneén.

Til toppen