The first theatre on the site at 217-223 Bourke Street, Melbourne was the Victorian Academy of Music, built for Samuel Aarons, which opened with a performance by Ilma de Murska on 6 November 1876.

[6]In 1888-9, Wilson built the Palace Hotel next door, behind existing shops at 227-223 Bourke Street, accessed via the Victoria Arcade.

[8][9] A new, larger Bijou Theatre seating up to 2000 with two balconies and six boxes was built on the site, designed by George Johnson, opening in early 1890.

In 1915 Ben Fuller management bought the freehold of the Palace Hotel and the Gaiety, and the lease of the Bijou,[13] and promoted it as the 'Home of Clean Vaudeville', with performers included 'Stiffy', 'Mo' and George Wallace.

[2][14] In 1930, the Gaiety was converted to a full time cinema renamed the Roxy, with Fullers announcing grand plans for the whole complex, and closing the hotel.