Building work began in 1900 and the theatre opened on 27 May 1901 as the Lyceum Theatre, with its entrance on John Bright Street and a design by the architects Owen and Ward. Business was slow at first, so a star was brought in: Harry Arthur Saintsbury led the company in costume dramas for ten weeks from the middle of June 1901. Returns remained disappointing and the theatre was sold to Lester Collingwood for £4,000, who renamed it the Alexandra Theatre on 22 December 1902.
After Collingwood was killed in a road accident in 1910, Leon Salberg took over, and the Salberg family ran the theatre from 1911 to 1977. Under Leon Salberg the Alex became known for its pantomimes, among them Mother Goose, and in 1935 the building was rebuilt with a fine Art Deco auditorium designed by Roland Satchwell. Leon died in his office at the theatre in 1938 and his son Derek succeeded him; Derek's memoir, My Love Affair with a Theatre, appeared in 1978 with a foreword by Laurence Olivier. Local loyalty ran deep: in 1950, 85 per cent of season ticket holders lived within Birmingham's boundaries.
Between 1967 and 1969 a new main entrance block went up on Suffolk Street to a design by the John Madin Design Group, joined to the older building by a wide bridge so that the whole reads as one theatre from inside. Satchwell's interior was refurbished in 1992 by the Seymour Harris Partnership, the same year the theatre staged the world premiere of Leslie Bricusse's Scrooge: The Musical with Anthony Newley. The Alex was home to the D'Oyly Carte Opera Company from 1990 to 1997, and under Apollo Leisure, which took over on 7 August 1995, investment in the stage and front of house allowed it to host major touring productions.
Ownership passed to SFX Entertainment in 1999, to Clear Channel in 2001 and to Live Nation in 2006, before the theatre came to the Ambassador Theatre Group, which for a time renamed it the New Alexandra Theatre. On 17 September 2018 it was relaunched as The Alexandra following a £650,000 refurbishment. It reopened in July 2021 after the COVID-19 closures, in its 120th year, and in November 2024 presented the world premiere of the jukebox musical Here and Now. The theatre has its share of stories, too: Neville Chamberlain spoke here on 13 October 1918, Arthur Lowe was taken ill in his dressing room in 1982, and Leon Salberg's ghost is said to have stayed on.