بدأ مسرح فيكتوريا بالاس كقاعة حفلات صغيرة فوق فندق «رويال ستاندرد» (بُني عام 1832). وفي عام 1850، جرى توسيع المبنى وتحولت القاعة إلى «قاعة موسيقى مويس» (Moy’s Music Hall). لم يدم هذا الاسم طويلاً، وبحلول 1863 أصبح يُعرف بـ«قاعة موسيقى رويال ستاندرد». ثم هُدم المبنى وأُعيد بناؤه مرتين لاحقاً (1886 و1910)، ومع الاسم الجديد «فيكتوريا بالاس» قدّم عروض المنوّعات وعروض الريفيو الاستعراضية. وقد أدّت جذور المكان كقاعة موسيقى إلى ردود فعل متباينة عندما حاول المسرح الانتقال إلى أعمال أكثر نضجاً. فعلى سبيل المثال، مسرحية وطنية بعنوان «يونغ إنغلاند» (Young England) قوبلت بسوء شديد من النقّاد إلى حد أنها تحولت لاحقاً إلى عمل ذي شعبية cult. أثبتت العودة إلى الريفيو أنها أكثر ربحية، مع عروض مثل «مي آند ماي غيرل» (1937)، و«ذا كريزي وانز» (سلسلة من عروض الريفيو الكوميدية بين 1947 و1962)، و«عرض المنسترل الأسود والأبيض» (الذي عُرض طوال الستينيات حتى 1972). كما حققت المسرحيات الموسيقية نجاحاً كبيراً للمسرح، إذ استمر عرض «قصة بادي هولي» (The Buddy Holly Story) لمدة 13 عاماً (منتقلاً إلى مسرح ستراند عام 1995). واستمر هذا النهج في القرن الحادي والعشرين، مع عروض مثل «فيم» و«غريس»، إلى جانب العرض الأول لمسرحية «بيلي إليوت».