Das Victoria Palace Theatre begann als kleiner Konzertsaal über dem Royal Standard Hotel (erbaut 1832). 1850 wurde das Gebäude erweitert und der Raum wurde zur Moy’s Music Hall. Dieser Name hielt nicht lange, und bereits 1863 hieß es Royal Standard Music Hall. Das Gebäude wurde später zweimal abgerissen und neu gebaut (1886 und 1910) – nun unter dem Namen The Victoria Palace, mit Varieté-Programmen und Revuen. Die Music-Hall-Wurzeln des Hauses führten zu gemischten Reaktionen, als das Theater versuchte, sich in Richtung eines „erwachseneren“ Spielplans zu entwickeln. So wurde etwa das patriotische Stück Young England von der Kritik derart verrissen, dass es ausgerechnet zum Kult-Hit wurde. Die Rückkehr zur Revue erwies sich als einträglicher: mit Produktionen wie Me and My Girl (1937), The Crazy Ones (eine Reihe komödiantischer Revuen von 1947 bis 1962) und der Black and White Minstrel Show (die in den 1960er-Jahren bis 1972 lief). Auch Musicals waren für das Theater ein Erfolg: The Buddy Holly Story lief 13 Jahre lang (1995 ans Strand Theatre übertragen). Dieser Trend setzte sich im 21. Jahrhundert fort – mit Fame, Grease und der Uraufführung von Billy Elliot.