The first steps of construction took place in 1952, when Coventry's twin city of Belgrade, Yugoslavia (now Serbia), pledged a gift of beech timber to be used in the new theatre.

[9] The Belgrade was officially opened at 8 pm on 27 March 1958 by the Duchess of Kent in a ceremony attended by many "civic personalities and representatives of the theatre world" including Sir Kenneth Clark and Sam Wanamaker.

[10][11] Coventry's first female Lord Mayor, Pearl Hyde, gave an address of welcome and thanks to the Duchess from the Royal box before the first show began, Half in Earnest by Vivian Ellis.

[15] The theatre received a number of grants for maintenance and renovation through the 1980s[16] and 1990s,[17] before a major refurbishment was announced as part of Coventry's Millenium project.

[18] It was closed in 2006 for extensive building work including the addition of a new performance space, which took ten months longer than expected, but was completed fully funded at a total cost of around £14 million.

[22] A further capital project to expand and upgrade facilities (architects Corstorphine & Wright) was completed fully funded in 2021 despite the Pandemic, with an adjacent shop being seamlessly absorbed into the footprint resulting in an enlarged stylish cafe and glamorous new first floor Bar called 1958.

[23] Led by Artistic Director Hamish Glen (2003 to 2021) the Belgrade was involved in the bid for Coventry to become UK City of Culture 2021, which it won in December 2017.

The Coventry City Architect's Department under Donald Gibson produced a model in 1944 that showed three interlinked theatres and cinemas arranged radially around a quarter circle shaped car park, centred roughly on the site of the Belgrade.

[29] Through the late 1940s and early 1950s it became increasingly clear that only one theatre was needed, so Arthur Ling began work on the building that stands there today.

The south east elevation is reminiscent of Gibson's Broadgate House (1948–53) with an arcade of shopfronts underneath a brick-clad block of flats for visiting actors, with regular square windows framed with pale stone.

[32] Ling utilised the gift of beech timber from Belgrade to panel the inside of the auditorium, which was fitted out in the style of the Royal Festival Hall.

[33] The extension opened in 2008 was designed by Stanton Williams, "contrasting [the] use of coloured renders and translucent panels" to "signal [...] presence within an evolving cityscape".