Commissioned by impresario Richard D'Oyly Carte in the late 1880s, it was designed by Thomas Edward Collcutt. Carte intended it to be the home of English grand opera, much as his Savoy Theatre had been built as a home for English light opera, beginning with the Gilbert and Sullivan series. The foundation stone, laid by his wife Helen in 1888, can still be seen on the façade of the theatre, almost at ground level to the right of the entrance. The Palace Theatre's current capacity is 1,400.

The theatre opened as the "Royal English Opera House" in January 1891 with Arthur Sullivan's Ivanhoe. No expense was spared to make the production a success, including a double cast and "every imaginable effect of scenic splendour. It ran for 160 performances. However, this was not enough to sustain the venture. Sir Henry Wood, who had been répétiteur for the production, recalled in his autobiography that "[if] Carte had had a repertory of six operas instead of only one, I believe he would have established English opera in London for all time. Towards the end of the run of Ivanhoe I was already preparing the Flying Dutchman (opera) with Eugène Oudin in the name part. He would have been superb. However, plans were altered and the Dutchman was shelved." Carte sold the theatre within a year, and it was renamed the Palace Theatre of Varieties.

In March 1897, the theatre began to screen films from the American Biograph Company as part of its programme of entertainment, these films pioneered the 70 mm format which helped give an exceptionally large and clear image filling the proscenium arch. The performances included early newsreels from around the world, many of them made by film pioneer William Kennedy Laurie Dickson, including film of the Anglo-Boer War (1900). The Palace continued to shows films as part of its variety and musical programmes.

The name of the theatre was finally changed to The Palace Theatre in 1911. On March 11, 1925, the musical comedy No, No, Nanette opened at the Palace Theatre starring Binnie Hale and George Grossmith, Jr.. The run of 665 performances made it the third longest running West End musical of the 1920s. The Palace Theatre was also the venue for Fred Astaire's final stage musical Gay Divorce which opened there on November 2, 1933.

The last decades of the twentieth century saw two exceptional runs at The Palace: Jesus Christ Superstar and Les Misérables. The latter ran for eighteen years, having transferred from the Barbican Centre on December 4, 1985. The show is still running at the Queen's Theatre just 100 metres further up Shaftesbury Avenue, having transferred there in April 2004. On October 8, 2006, it became the longest running musical in the world, overtaking the former record set by CATS.

In August 1983, Andrew Lloyd-Webber announced that he had purchased the freehold of the theatre for £1.3 million and subsequently set out on a series of works to restore the theatre. During work on the auditorium, a layer of plum-coloured paint was removed, revealing the famous marble and onyx panels to be untouched. Following the transfer of Les Miserables, the theatre was greatly refurbished, marble walls uncovered, restored, repainted, new chandeliers, cleaned etc. This was followed by a short 6-week season of illusionist Derren Brown following his successful UK tour. Andrew Lloyd Webber's The Woman in White received its world premiere on September 15, 2004 and ran for 19 months to February 25, 2006. The show outlived the Broadway version, playing at Broadway's Marquis Theatre, where it opened in November 2005, by 6 days. Bill Kenwright's production of Andrew Lloyd Webber and Jim Steinman's musical Whistle Down The Wind played from March 15 - August 12, 2006.