The Victoria Palace Theatre foi projetado pelo arquiteto de teatro Frank Matcham e abriu suas portas pela primeira vez em 1911, apresentando uma variedade de revistas e pequenos musicais. As primeiras produções incluíram The Chelsea Follies (1930), Young England (1934) e Me and My Girl (1937).
Espectáculos subsequentes foram uma selecção de espectáculos de variedades que começaram no pós-guerra, seguidos por The Crazy Gang (1947) e o espectáculo de longa duração Black and White Minstrel Show (1962-1972), seguido por Carry On London (1974) e Elizabeth Taylor em The Little Foxes (1982).
A década de 80 viu produções incluindo Charlie Girl (1986), musical High Society (1987) e Buddy – The Buddy Holly Story (1989-1995), assim como Jolson (1995), Fame – The Musical (2000), Kiss Me Kate (2002), Grease (2002-2003) e Tonight’s the Night (2003-2004).
2005 viu o longa-metragem Billy Elliot the Musical abrir no teatro, baseado no filme de sucesso de Lee Hall. A produção estrelou originalmente Tim Healy e Haydn Gwynne, passando por uma série de rostos famosos, incluindo Ruthie Henshall, antes de fechar em 2016 para sofrer uma remodelação multimilionária.
Novembro de 2017 viu o Victoria Palace Theatre reabrir com o musical de Lin-Manuel Miranda da Broadway, que continua a tocar para audiências esgotadas.