Всесвятская церковь являлась самой поздней по времени построения из мценских храмов. Место, на котором ее возвели, издревле принадлежало мужскому Петропавловскому монастырю. Изначально это была часовня во имя Кирика и Иулитты. Вместо нее в 1857-1860 гг. попечением архимандрита Иерофея была построена кирпичная церковь. В 1839 г. Мценск посетил известный филолог и славист Измаил Иванович Срезневский, сделавший небольшую зарисовку часовенки, являющуюся её единственным сохранившимся графическим изображением. В 1848 г. часовню обновили на средства неизвестного благотворителя и прежнее деревянное покрытие заменили железным. По свидетельству современника, «кроме нескольких ветхих икон и лампад, в часовне ничего нет. При ней в особой деревянной келии живут постоянно два монастырских послушника для надзора за нею и сбора доброхотных подаяний. Ежегодно 15 июля к часовне из монастыря устраивался крестный ход. Архимандрит Иерофей, много сделавший для обустройства Петропавловского монастыря, обратил внимание на приписанную к нему запущенную часовню, и благодаря его хлопотам, ходатайству Орловского епархиального начальства и архиепископа Орловского Смарагда было разрешено устроить на ее месте церковь, каковая и была, после утверждения ее плана в губернской строительной комиссии, возведена в 1857–1860 гг. и освящена во имя Всех Святых архимандритом Иерофеем «соборне». Но храм, располагавшийся рядом с главной улицей города, вскоре оказался тесен для разросшегося прихода, и в 1887 г. тщанием архимандрита Иоасафа его расширили пристройкой двух освященных 16 апреля 1888 г. приделов: во имя Св. великомучеников Кирика и Иулитты и Св. Царевича Иоасафа. Храм был сооружен в господствовавшем в то время в русской архитектуре «русском» стиле и являлся единственным произведением подобного рода в городе, и, надо признать, довольно удачным.
Церковь внутри была богато отделана. Согласно отчету архимандрита Иоасафа, «настоящий (главный) иконостас Всесвятской липового дерева, с резными вызолоченными колоннами, вся резьба в иконостасе вызолочена червонным золотом, иконы живописныя. На северной стороне в приделе сооружен иконостас изящной работы с колоннами и вызолоченной резьбою, иконы живописныя, поля коих вызолочены». К храму была пристроена небольшая кирпичная колоколенка, на которой висели пять колоколов, «из коих больший весом 20-ть пуд». На церковном участке, кроме того, устроили деревянный дом для помещения братии, отправлявшей богослужение, и три лавки, обращенные фасадами на соседние улицы, одна из которых предназначалась для торговли книгами.
В 30-е годы Всесвятскую церковь постигла участь всех остальных мценских храмов. Она была закрыта, ее имущество разграблено, а сам храм разрушен. Но, по воспоминаниям очевидцев, какая то часть его, которую местные жите ли называли «часовней», еще стояла после войны и, более того, в ней шла служба. Но вскоре ее закрыли, а храм доломали окончательно. В настоящее время даже затруднительно определить точное место, где когда то находилась Всесвятская церковь.
Источник: В. Неделин "Архитектурные древности Орловщины (ушедшее)". Стр. 106-107
4 апреля 2017