Built circa 1909 by Horsfall & Sons as a music hall on the former site of the Rose and Crown Hotel (demolished 1884), it was later converted into a theatre. The building was destroyed internally by fire on 23 January 1936, but was rebuilt in the Art Deco style by architect Roland Satchwell and reopened as the New Palace Theatre the following year.
The theatre reportedly closed in 1954 but was reopened at Easter 1955 after modernisation and redecoration. However, a "lack of public support" led to closure again on 17 August 1957.
It was briefly reopened as the cabaret Continental Palace Theatre before being converted to a bingo hall in the 1960s. In 1998, it became the Chicago Rock Café and later the Society nightclub, eventually closing in 2010.
The building was then threatened with demolition as part of the proposed extension of the Kingsgate Shopping Centre. The Palace Theatre Restoration Trust was formed in 2011 with the intention of returning the building to theatrical use. In 2012, a planning application by the owner to convert the former theatre into student accommodation was successful and the work was carried out in 2014.
Whilst the recent conversion saw the removal of the theatre's Art Deco interior, the exterior of the building was restored. The building is now called the Palace Studios.