' Sanctuary ' първо се появила в компилацията Metal For Muthas и не била включена в Англо/Европейската версия на албума до преиздаването му през 1998. Тя е вторият сингъл на Maiden , който се издигна до 29-то място в Британските класации. Това е бърза и енергична песен за един престъпник, бягащ от закона (тема, която по-късно се появява в още няколко песни на Maiden включително ' Murders In The Rue Morgue ', ' Innocent Exile ', и ' The Fugitive ').

Изречението "Никога не съм убивал жена досега, но знам какво е усещането" е много интригуващо. За кого се отнася? Възможно ли е това да е Еди, който убива Маргарет Тачър, както е нарисувано на плочата на сингъла. Това е обаче малко вероятно, тъй като илюстрацията е нарисувана след написването на песента и точно това е изречението, което е връхновило Дерек Ригс да нарисува убийството.