Originally located in Adelaide Street, Brisbane between Edward and Albert Streets, Albert Hall opened on 20 September 1881. It was remodelled in 1884 and renamed the Academy of Music, until 1886, when it was renamed the Gaiety Theatre. The original building was demolished in 1909, when purchased by Finney Isles.
The second Albert Hall was located on Albert Street, between Ann and Turbot Streets, and opened in 1901, the second level housing the Central Methodist Mission. The Queensland Government purchased the site and demolished the building to make way for the S.G.I.O. offices and new S.G.I.O. Theatre, subsequently renamed the Suncorp Theatre. The opening performance on 20 September 1881, was a concert by violinist August Wilhelmj.
Early companies that used the Gaiety Theatre as it was know during the 1890's were: Taylor Carrington Co., Wilson Forbes Dramatic Co., Hamilton's Dramatic Season, the Great Pantomime Co. and the Gaiety Pantomime Co. Featured artists were Florence Stanthorpe, The Beaumonts, Florrie Forde, Ada Delroy, as well as a Grand Concert on Sunday evenings.
The second Albert Hall was used by local muscial, choral and elocution groups as well as visiting performers, university drama societies and the Methodist Ladies Guild as a soup kitchen during the Depression. When the hall re-opened on 29 August 1940, "A Patriotic Concert" was held.
From the 1940's the hall was used by the Twelfth Night Theatre Co., as well as the Brisbane Arts Theatre, The Brisbane Repertory Theatre Society and the Brisbane Opera Society. In the 1960's Musica Viva staged its concerts at the hall. The final performance was a Gala Review on 28 April 1968.