Founded by brothers Vaiben and Emanuel Solomon, the Queen's Theatre is the oldest surviving theatre building in mainland Australia. It cost an astonishing £10 000, and attracted dismal forecasts from the local press. The opening performance of Othello took place in January 1841. At the time the Queen's Theatre seated 1000. Performances were shortlived, by August 1841 the company was dismissed and in 1842 the Solomon brothers were looking for other ways to make money from the site. In 1843 the Colonial Government took over the building for the Resident Magistrates Court and Supreme Court.
In 1850 the law courts moved to new premises in Victoria Square. The Queen's Theatre was remodelled with a new Georgian facade and re-opened in December 1850 as the Royal Victoria Theatre. A year later it closed again, due to a mass exodus of South Australians to the Victorian goldfields. In 1859 more renovations were undertaken and another attempt made to operate a theatre from the site. However, competition from the newly-opened Theatre Royal on Hindley Street in April 1868 effectively sealed its fate, and the Queen's Theatre closed its doors yet again later that year.
Between 1868 and 1973 the building was adapted for a variety of non-theatrical uses. It operated as the City Mission between 1872 and 1876, and as Formby's Horse Bazaar from 1877 until shortly after the turn of the twentieth century. Between 1908 and 1928, the sales yards, livery, stables and forge owned by J.W. Shannon utilised the premises. It changed hands three more times between 1933 and 1973, operating as McPherson's Store and Warehouse, Dalgety's Factory and Store, and McPherson's Showroom, respectively.
Proposed development of the site during the late 1980s prompted an archaeological excavation that uncovered extensive sub-surface remnants of the former Queen's Theatre. These features included dressing rooms and the orchestra pit. The site's heritage significance prompted the South Australian Government to negotiate for its ownership during the 1990s and, upon acquiring the property, initiate efforts to conserve its surviving heritage architecture. Today, the shell of the original theatre still stands within the 1850s facade of the Royal Victoria Theatre.
Since 1996 the building has once again been used as a venue for performances, but also frequently hosts non-theatrical events such as markets, corporate functions, and art exhibitions. Strict conditions have been put in place to preserve the historic character of the building. The History Trust of South Australia managed the Queen’s Theatre from 18 August 2003 until 1 July 2010. It was then taken on by Arts South Australia, and is currently managed by GWB McFarlane Theatres.