Het Palace Theatre opende in januari 1891 zijn deuren met de ambitie hét huis van de Engelse Grand Opera te worden. Onder de oorspronkelijke naam 'The Royal English Opera House' waren de eerste twee producties (Ivanhoe en La Basoche) weliswaar succesvol, maar er lag geen nieuw repertoire klaar om de zaal te vullen. Slechts een jaar later werd het theater al verkocht, verbouwd tot een statige music-hall en omgedoopt tot het Palace Theatre of Varieties. In 1904 wisselde het theater opnieuw van eigenaar; de nieuwe manager Alfred Butt legde de nadruk op een gevarieerd programma, variërend van dansgroepen tot vroege filmvoorstellingen (die daar al sinds 1897 te zien waren). In 1911 werd de naam ingekort tot simpelweg 'The Palace Theatre', waarna het in de rest van de 20e eeuw het decor vormde voor talloze memorabele voorstellingen. In 1922 verwelkomde het theater de legendarische Marx Brothers, die er fragmenten uit hun Broadway-shows speelden. De komische musical No, No, Nanette opende in 1925 en was goed voor maar liefst 665 voorstellingen. Andere successen uit die tijd waren onder meer Princess Charming (1926), The Girl Friend (1927) en Gay Divorce (1933) – de laatste toneelmusical met Fred Astaire. De reeks musicalsuccessen zette gestaag door met The Sound of Music (die in 1961 opende en 2.385 keer werd opgevoerd), Jesus Christ Superstar (1972-80) en Les Misérables (1985), dat maar liefst 19 jaar in het Palace stond voordat het verhuisde naar het Queen’s Theatre. Recente publiekstrekkers zijn onder andere The Woman in White (2004-06), Spamalot (2006-09) en Priscilla Queen of the Desert (2009-11).