O ano era 1980 e o Iron Maiden estava em uma grande turnê de divulgação do seu primeiro álbum. A banda também já havia lançado um single para "Running Free" e em meio à divulgação da turnê a gravadora EMI se apressou em lançar um novo single, para coincidir com as datas dos shows, e o Maiden, sabiamente, optou por uma regravação de "Sanctuary", a faixa incluída na coletânea Metal for Muthas, que não estava originalmente no álbum, mas era uma grande favorita dos fãs que já tinham visto a banda ao vivo.
Construída em torno do riff de sirene de polícia de Dave Murray e dos vocais brutais de Paul Di’Anno, "Sanctuary", que tem 3 minutos e 13 segundos de puro metal, é tão capciosa e sangrenta como um gancho de açougue. A nova versão era considerada pela banda e pelo público bem melhor que a original e a crescente legião de fãs correu para comprá-lo nas duas primeiras semanas após o lançamento, o que mandou o single para a 33ª posição na lista dos mais vendidos. Uma semana depois “Sanctuary” subiu ainda mais, atingindo como uma bomba o número 29 das paradas nacionais, e, mais uma vez, sem o apoio das rádios.
Mas um fator contribuiu ainda mais para o sucesso do single. Derek Riggs criou um Eddie para a capa que não só captou soberbamente a atmosfera da música, mas também causou grande controvérsia para a banda. Um Eddie, brandindo uma faca, estava agachado sobre a figura de uma mulher morta vestindo saia que, com um olhar mais apurado, parecia ser Margaret Thatcher, a conservadora ocupante do cargo de primeira-ministra que havia chegado ao poder na Inglaterra nas eleições de 1979. A julgar pela cena, Eddie havia, aparentemente, flagrado a autoridade máxima do país no imperdoável ato de rasgar um pôster do Iron Maiden, arrancando de um muro na rua: um crime - aos olhos enlouquecidos do Eddie - passível de punição imediata. O sangue ainda pingava da sua lâmina, de doze polegadas, no momento em que o vemos. Mas o lançamento do single coincidiu com uma série de atos de violência na vida real, perpetrados por vários membros descontentes do povo inglês contra diversos integrantes oficiais do governo (Lorde Home foi perseguido por uma gangue de skinheads na estação de metrô Piccadilly Circus, e Lorde Chalfont ganhou um olho roxo ao topar com um jovem enquanto caminhava na King’s Road).
Em entrevista para o escritor Mick Wall o empresário Rod Smallwood comentou o lançamento e revelou detalhes importantes de tudo que aconteceu na época: "A arte era bastante bem-humorada, como sempre. Na época, Maggie [Margareth Tatcher] tinha visitado a antiga União Soviética e, seguindo sua dura postura com eles, ganhou o apelido de "Dama de Ferro" [Iron Lady]. Eddie não gostou disso, e muito menos quando ela começou a arrancar os pôsteres da banda. Ainda é uma das minhas artes prediletas. Pouco antes de ser publicada eu sugeri à EMI que colocassem uma venda preta nos olhos dela, já que isso daria um ângulo para noticiar nos tabloides e chamaria a atenção para o single. Funcionou, e conseguimos uma grande cobertura.”
Em 20 de maio de 1980, The Daily Mirror reproduziu a versão sem censura da capa de "Sanctuary", sob a manchete: "É assassinato! Maggie é atacada pelo rock!". Logo, foram feitas perguntas no Parlamento. "A premiê Margaret Thatcher foi assassinada – na capa do disco de uma banda de rock", relatou em tom de choque o The Mirror. De forma hilária, o jornal inglês citou a declaração de um porta-voz do governo: "Não é dessa maneira que gostamos de ser retratados. Tenho certeza de que ela não gostou". Trazendo a mesma história, o The Daily Record, um irmão escocês do The Mirror, disse ter achado a capa de "extremo mau gosto", acusando a banda de capitalizar em cima de um "artifício barato". Paul Di'Anno disse que a aborrecida PM [primeira-ministra] teria até mesmo instruído seu procurador a enviar uma carta para a banda, expressando uma visão parecida, mas nem Steve nem Rod se recordam de tê-la recebido, de forma que é melhor denotar tal carta como mais um exemplo da imaginação ativa de Paul.
Ao longo do caminho, naquele mesmo ano o Iron Maiden também faria seu próprio show no tradicional Rainbow Treatre, de Londres, pela primeira vez, quando a gravadora os ajudou a celebrar dando uma festa pós-show para a banda e para centenas de convidados no Museu de Cera Madame Tussaud’s Chamber of Horrors. A festa rendeu a curiosa foto abaixo com uma Margaret de cera.
