The first record of a church dedicated to the Intercession of the Virgin Mary in the city came in 1615. This original church was constructed out of wood and the present-day stone replacement was built between 1736 and 1796 in the classical style. The church was further reconstructed in the mid-19th century. The cathedral was closed in 1932 but reopened in 1948 when it became the eparchial cathedral of the Voronezh Eparchy. In 1989 the relics of St Mitrofan of Voronezh were transferred here from the Voronezh Regional Museum and remained at the church until they were transferred to the newly built Ascension Cathedral in 2009.