В июле 1834 г. губернский архитектор Иван Андреевич Блицын (1780-е - после 1841) выполнил проект церкви во имя Всех Святых. Один из приделов решено было посвятить святителю Митрофану Воронежскому, только что канонизированному Русской Церковью. В ноябре 1835 г. чертежи рассмотрели в Петербурге и утвердили, в следующем году началось строительство. 25 мая 1841 г. архимандритом Елпидифором (Бенедиктовым) освящен придел во имя святого Митрофана, находившийся в правой части трапезной, в 1842 г. уже ставший викарным епископом Елпидифор освятил придел во имя преподобной мученицы Евдокии, расположенный в левой части трапезной...
Целиком же Всесвятская церковь была завершена к 1851 г. и освящена викарным епископом Феогностом (Лебедевым). По архитектуре церковь была близка к храмовой части нынешнего Покровского собора, да и строились они практически одновременно. Ее тоже относили к образцам «благородного, выдержанного классицизма». Это обстоятельство и дает возможность предположить в обоих случаях авторство одного и того же архитектора И.А. Блицына.
Долгое пятнадцатилетнее строительство небольшого храма объясняется тем, что он возводился на частные пожертвования купчихи Евдокии Сергеевны Аврамовой (1782-1867), церковного старосты Ивана Ивановича Аврамова, купцов Александра Петровича Борисова (1781-1869), Антона Родионовича Михайлова (1804-1874), Ивана Михайловича Кривошеина. Их попечительством содержался первое время и церковный причт. Среди горожан церковь приобрела название Новостроящейся, и кладбище, вместо официального названия Новомитрофановское или Всесвятское, тоже именовалось Новостроящимся. В конце 1860-х гг. при ремонте храма стены его трапезной отделали под мрамор.
В ноябре 1842 г. на окраинном кладбище был похоронен безвременно ушедший из жизни поэт Алексей Кольцов, чуть позже рядом с ним оказалась сестра Анисья (1820-1847), в замужестве Семенова, потом родители, Василий Петрович (1778-1849) и Прасковья Ивановна (1784-1861). В 1861 г. буквально напротив погребли поэта Ивана Никитина. Так было сделано сразу - поэт упокоился подле поэта, и могилу Никитина не переносили сюда позже, как иногда приходится слышать. На одной из дореволюционных фотографий можно увидеть табличку с надписью: «Дорожка к могилам Кольцова и Никитина».
В те времена кладбище было ухоженным, на могилах стояли надгробные памятники из гранита и мрамора. Слева от церкви на фамильном склепе Клочковых возвышалась часовня, спроектированная их родственником архитектором C. Мысловским. У алтаря церкви была похоронена благотворительница Е.С. Аврамова, недалеко от нее - юродивая старица Христина († 1866), над могилой которой купцом В.Н. Студенцовым была сооружена часовня; выделялась среди окрестных захоронений могила духовного писателя Луки Ефремова (1788-1877).
В середине 1930-х гг. использование старого кладбища прекратилось. Церковь закрыли раньше. Судьба полуразрушенной церкви окончательно определилась в августе 1964 г., когда на заседании градостроительного совета принималось решение о возведении в парке культуры цирка. Его намеренно отодвигали в глубь участка на сто метров, чтобы сохранить возможность «в будущем организовать рациональную транспортную развязку в двух уровнях на пересечении улиц 20-летия Октября и Кирова». Цирк вместимостью 2100 мест строился по типовому проекту: он повторял здание в Новосибирске. Привязку к местным условиям производил архитектор А.Г. Бузов. На месте Новостроящегося кладбища работы начались в 1965 г. разрушением Всесвятской церкви.
Использованная литература: А.Н. Акиньшин "Храмы Воронежа"; П. Никольский "Справочная книга для духовенства Воронежской епархии. 1900"
http://rustemple.narod.ru/voronezh_vsesvyatskaya.html