After Catherine the Great banned burials in city centres, the Vsekhsvyatskoe Cemetery was founded in 1771 on what was then the outskirts of the city. The All Saints Cathedral was built for this cemetery between 1773 and 1776 in the classical style. A tall three-tiered bell tower was added in 1825. The church remained opened throughout the whole Soviet era, although from 1923 to 1943 it was part of the Renovationist Church. Since 1944 it has been an eparchial cathedral and is now the eparchial cathedral of the Tula and Yefremov Eparchy of the Tula Metropolitanate. The remains of St John (Ioann) of Tula were held here until 2007 when they were transferred to the Dormition Cathedral.