بُني مسرح أبولو فيكتوريا عام 1929 بطراز آرت ديكو وبديكور داخلي مستوحى من الأجواء البحرية، وافتتح أبوابه في 15 أكتوبر 1930. لكن عند افتتاحه كان يحمل اسم «نيو فيكتوريا سينما»، وكان يعرض مزيجاً من الأفلام وعروض المنوعات، قبل أن ينتقل بعد بضع سنوات إلى استضافة حفلات فرق البيغ باند. وفي عام 1939 اختيرت السينما لعرض «ديربي إبسوم» قبل أن تُغلق في 1940 بسبب الحرب العالمية الثانية. ولحسن الحظ تعرّض المبنى لأضرار محدودة، فأُعيد افتتاحه بسرعة بعد عام. وبعد نجاته من خطط الهدم في خمسينيات القرن الماضي، ومع سنوات عدة قدّم خلالها الباليه والأفلام والترفيه الحي، عُرضت آخر الأفلام في هذا المكان في نوفمبر 1975: عرض مزدوج لأفلام رعب هما Legend of the Werewolf وVampire Circus. وشهد عام 1981 افتتاح المبنى باسم «أبولو فيكتوريا». قُدّمت في أوائل الثمانينيات عروض The Sound of Music وCamelot وFiddler on the Roof، قبل أن يُعاد تشكيل الداخل على نحو كبير من أجل Starlight Express، وشملت التعديلات إنشاء مضمار سباق يمر عبر المقاعد وبين الجمهور. استمر عرض Starlight Express لمدة 18 عاماً، ثم أُعيد ترميم الداخل وتطويره، ليصبح أول مدرّج مسرحي يُضاء بالكامل باستخدام مصابيح LED منخفضة الاستهلاك. وبعد عروض Bombay Dreams وSaturday Night Fever وMovin’ Out، استضاف المسرح في سبتمبر 2006 نجاح برودواي الكاسح Wicked. وقد حطمت العروض الثمانية الأولى أرقام مبيعات التذاكر القياسية، وخلال السنوات السبع التالية لافتتاحه حقق العمل إيرادات تجاوزت 150 مليون جنيه إسترليني.