Lyceum Theatre, der er tegnet af den berømte teaterarkitekt Bertie Crewe, åbnede første gang dørene d. 31. december 1904 for at markere indgangen til et helt nyt år. Bygningen er anført på den engelske liste over bygninger af særlig arkitektonisk eller historisk art.
Det teater, man ser i dag, er faktisk ikke det oprindelige. Helt tilbage i 1722 lå der er teater på stedet, der var tegnet af James Payne. Indtil gaslampernes tid blev teatrene oplyst af stearinlys, og det skabte en rigtig god atmosfære, men var usandsynligt farligt. Det første teater på stedet blev revet ned for at give plads til et nyt teater, der blev tegnet af Samuel Beazley, og som åbnede i 1815, som det første spillested i London oplyst af gaslamper.
Mozarts vidunderlige opera Cosi Fan Tutti fik engelsk premiere på teateret i 1823, men i 1830 blev teateret ramt af en katastrofe, da en brand raserede bygningen og den brændte ned til grunden. Heldigvis blev Samuel Beazley bedt om endnu en gang at tegne et Lyceum Theatre. Hans andet store designværk åbnede til stor ros 4. juli 1834 med en imponerende facade i oldgræsk arkitektur og en kæmpestor, tre etagers teatersal.
Datidens store navn, Henry Irving, der er synonym med Lyceum Theatre, bjergtog publikum med en legendarisk præstation i The Bells og med sin hovedrolle i Hamlet i 1874. Det samme år overtog Irving styringen af teateret og endte med at bestyre spillestedet i de næste 21 år. Irving måtte til sidst opgive sin stilling som leder af Lyceum, da han var plaget af både økonomiske og helbredsmæssige problemer. Hans sidste optræden på den store Lyceum-scene, som han elskede så meget, var i 1902, da han tryllebandt publikum i Shakespeares fortælling The Merchant of Venice (Købmanden fra Venedig).
Teaterets nye ejere, der stod over for stramme, nye sundheds- og sikkerhedsregler, valgte at genopbygge hele stedet fra grunden, frem for at lade det gennemgå dyre ombygninger. Nu blev den teaterelskende Bertie Crewe valgt til at skabe den bygning, som står på stedet i dag. Hvis man ser nærmere efter, kan man se, hvordan Crewe på dygtig vis har bevaret den originale græskinspirerede facade, og bare har bygget et helt nyt teater bag den.
I 1939 var teateret truet af nedrivning grundet en stor sanering af området. Det var faktisk så tæt på, at man havde solgt møblerne og det faste inventar på auktion. Men spillestedet reddede skindet i sidste øjeblik, da Anden Verdenskrig brød ud, og nedrivningsplanerne blev skrinlagt. Teateret stod tomt og ubrugt indtil 1945, hvor det blev overtaget af Mecca Ltd. Og genåbnede som en dansesal.
I løbet af 1960'erne og 1970'erne blev spillestedet hjem for pop-koncerter frermført af diverse musikkunstnere som eksempelvis The Who, Bob Marley, U2 og Culture Club. I 1985 rykkede The National Theatre dets opsætning af The Mystery Plays, der var bearbejdet af digter og skuespilforfatter Tony Harrison, til Lyceum.
I 1994 overtog Apollo Leisure stedet, og de istandsættelse det fuldstændig til dets tidligere glans mere overdådigt og dramatisk end nogensinde før. Den første produktion i de nye lokaler kom på scenen i 1996 og var en genopsætning af Andrew Lloyd Webber og Tim Rices musical Jesus Christ Superstar.
Disneys musikalske teatergenfortælling om The Lion King (Løvernes konge) kom til Lyceum Theatre i 1999, og henrykker den dag i dag publikum fra hele verden.