Деревянный храм был возведен в 1706 году в честь иконы Божией Матери "Всех скорбящих Радость" и служил Павловским подворьем Битюцкого Троицкого монастыря.
В 1761 году архимандрит Битюцкого монастыря Варсонофий доносил епископу Воронежскому Кириллу (Ляшевецкому) о крайней ветхости церкви и просил продать её желающим, т.к. на ремонт у монастыря не было средств. Но павловчане просили оставить эту церковь в городе, так как она существовала почти с самого начала его основания, и многие родственники были около неё похоронены. Вероятно, после обновления церковь была освящена в честь Смоленской иконы Божией Матери.
В 1831 году храм был выстроен в камне в виде ротонды, без колокольни. На церкви был устроен шпиль с главою. Внутри было восемь колонн, образующих собой ротонду; между колоннами и наружными стенами - галерея, сверху с трех сторон - хоры. Вместимость церкви была не более, как на 60 человек.
В 1882-1884 годах к церкви были пристроены две боковые главы, что придало ей "какой-то растянутый, некрасивый вид".
В 1930-е годы храм был разрушен. Сейчас территория кладбища застроена.
Источник - сайт drevo-info.ru