Zespół założony został w Boże Narodzenie 1975 roku. Inicjatorem jego powstania był dziewiętnastoletni basista Steve Harris. Harris urodził się 12 marca 1956 roku w Leytonstone, we wschodnim Londynie. W wieku młodzieńczym pasjonowała go przede wszystkim piłka nożna, czas na muzykę przyszedł dopiero później. Rockiem zainteresował się dzięki znajomemu, który udostępniał mu płyty takich zespołów jak **Jethro Tull** i **Deep Purple**. W wieku lat siedemnastu zapragnął zostać basistą, lecz najpierw postanowił poznać tajniki gry na gitarze klasycznej. Po jakimś czasie udało się zorganizować z kumplami zespół o nazwie **Influence**, który potem przechrzczono na **Gypsy’s Kiss**. Kapela zaliczyła parę występów i rozpadła się, a niespełna osiemnastoletni Steve załapał się do zespołu **Smiler**, grającego głównie kawałki z repertuaru **Wishbone Ash**. Pozwoliło mu to zdobyć nieco muzycznego doświadczenia, zwłaszcza dzięki koncertom w klubach. Już grając w **Smiler** Steve jednak wiedział, że chce grać swoją autorską muzykę. Ostatecznie opuścił zespół i zaczął poszukiwać muzyków do kapeli, która realizowałaby od początku do końca jego własną muzyczną wizję . Steve gorączkowo zabrał się więc za poszukiwanie odpowiednich muzyków. Szybko uporał się też ze zmorą wielu początkujących kapel – udało mu się znaleźć dla zespołu wyjątkowo trafną nazwę. **Iron Maiden** - "Żelazna Dziewica" - średniowieczne narzędzie tortur. Nazwa niebanalna, a jednocześnie prosta, sugestywna, pasująca do heavy metalu stała się wkrótce symbolem. Znana jest każdemu, kto choć trochę interesuje się rockiem. W pewnym okresie zyskała nawet dodatkowy wymiar - określeniem Iron Maiden (w znaczeniu Żelazna Dama) nazywano niezbyt popularną premier Wielkiej Brytanii Margaret Thatcher, którą zespół Steve'a odważył się "zamordować" na okładce singla **Sanctuary**.