Ouvert le 26 décembre 1910, le Palladium (ainsi nommé jusqu’en 1934) s’est rapidement imposé comme une salle de premier plan pour les spectacles de variétés — notamment la pantomime Cendrillon de 1926 (des images filmées de cette production existent encore aujourd’hui). Tout au long des années 1930, la troupe comique The Crazy Gang s’y est produite régulièrement, rencontrant un immense succès auprès du grand public comme de la Famille royale. À cette époque, les engagements étaient gérés par l’impresario Val Parnell. Pendant la Seconde Guerre mondiale, le théâtre a connu une alerte à la bombe lorsqu’une mine parachutée non explosée a traversé le toit. Une équipe de démineurs de la Royal Navy s’est rendue sur place et a réussi à la neutraliser. Parnell devient directeur général en 1945 et lance une politique audacieuse consistant à placer en tête d’affiche de grandes vedettes américaines. Parmi elles : Judy Garland, Bing Crosby, Bob Hope, Sammy Davis Jr et Frank Sinatra. La popularité des spectacles de variétés du Palladium s’amplifie encore grâce à l’émission d’ITV Sunday Night at the London Palladium, diffusée en direct pendant toute sa diffusion (1955-1967). En 1968, le théâtre présente sa première comédie musicale, Golden Boy, avec Sammy Davis Jr. Après un retour aux variétés dans les années 1980 (avec Live From the Palladium sur ITV1), le théâtre programme davantage de comédies musicales, dont Oliver! et Saturday Night Fever. Lorsque le Really Useful Group rachète la salle en 2000, cette tendance se poursuit. Le théâtre revient souvent à ses racines en accueillant des concerts (notamment d’Elton John) et en étant un lieu régulier du Royal Variety Performance (encore en 2013).