Согласно воспоминаниям строителя Ростовской крепости А. И. Ригельмана, две богадельни были основаны в крепости в 1768 году. Ещё одна богадельня была основана не позднее 1805 года, и в 1824 году её объединили с больницей.
Во второй половине XIX века было принято решение о строительстве в городе новой богадельни. 24 октября 1879 года для богадельни было отведено здание. Её было решено назвать Петропавловской в честь Новороссийского и Бессарабского генерал-губернатора Павла Евстафьевича Коцебу. Купец 2-гильдии Гавриил Ильич Шушпанов устроил в одной из комнат богадельни временный храм, он же был выбран первым старостой храма. 11 мая 1889 года ростовская городская дума дала разрешение на строительство отдельного храма при богадельне. Проект храма был разработан городским архитектором Н. А. Дорошенко. Средства на строительство храма были пожертвованы Г. И. Шушпановым. Храм был открыт в 1893 году[.
Основной престол храма был освящён в честь иконы Божией Матери «Всех Скорбящих Радость». В 1899 году в храме был устроен второй престол во имя Пантелеимона Целителя. Названия престолов были выбраны исходя из назначения храма. Старостой храма с 1900 года являлся потомственный почётный гражданин Иван Трифонов.
После 1920 года богадельня была закрыта. Храм стал приходским и некоторое время оставался действующим, но вскоре тоже был закрыт и снесён. Рядом с местом, где стоял храм, в 1931—1934 годах была построена гостиница «Ростов».
Малаховский Е. И. Храмы и культовые сооружения Ростова-на-Дону.
