В 1772 году высочайшим указом было запрещено погребать умерших в городской черте, у приходских церквей, и в связи с этим для городского кладбища было выделено место на Красной горе за Покровской церковью. 1 июля 1772 года из Успенского собора на новое кладбище совершен крестный ход и на месте будущей кладбищенской церкви установлен крест. 22 мая 1774 года из Успенского собора совершен крестный ход на отведенное кладбище и после молебна заложена деревянная церковь перевезенная из Сухонской Ерогодской волости с погоста Рождества Христова.
Церковь освящена 15 октября 1774 года во имя святого Стефана Великопермского. 4 августа 1799 года преосвященный Арсений, епископ Вологодский и Великоустюжский, дал грамоту на постройку каменной церкви Стефана Пермского. 30 июня 1800 года положено основание каменой церкви во имя Богоматери Всех Скорбящих Радости с приделами во имя святителя Стефана Пермского и во имя преподобного Феодосия Тотемского чудотворца. Строительство велось на средства прихожан под руководством купцов Ямщиковых. Колокольня Стефановской кладбищенской церкви построена одновременно с храмом. На ней имелось девять различной величины колоколов. Самый большой из них отлит в 1807 году, весил 107 пудов 30 фунтов и отличался от других отлитыми на нем изображениями Распятия Господня, Божией Матери и Николая чудотворца. Время изготовления и вес второго по величине колокола неизвестны. Третий колокол, весом в 12 пудов, был отлит в Устюге в 1786 году. Остальные колокола являлись малыми, ничем не примечательными.
В 1960-х годах выходит секретное постановление ЦК КПСС, подписанное тогдашним руководителем партии Никитой Сергеевичем Хрущевым, о полной ликвидации церквей на территории СССР. Местные власти обязаны были выполнять данное распоряжение партии и правительства. Великоустюгские власти вспомнили, что в городе две действующие церкви Прокопьевский собор и кладбищенская церковь. Решив, что на кладбище проверяющие и высокие начальники не ходят, постановлением исполкома Великоустюгского горсовета от 8 января 1964 года и 6 мая 1964 года здание Прокопьевского собора было закрыто, так как оно находится в центре города, а для пользования верующих оставлялось одно церковное здание, Стефано-Пермская кладбищенская церковь. В связи с этими постановлениями в кладбищенской церкви предстояло провести ремонтные работы, а именно, устройство иконостаса, парового отопления; настил полов в холодном храме и в средней части амвона и алтаря, очистку, шпаклевку и покраску холодного храма и алтаря, роспись теплого и холодного храмов, устройство хоров, тамбура и паперти, побелку наружных стен храма и покраску крестов на куполах и другие. Кроме того был упразднен придел теплого храма во имя Феодосия Тотемского, на его месте была установлена рака Прокопия Праведного перенесенная из Прокопьевского собора.
В 1965 — 1966 годах была покрашена крыша и купола храма, произведена позолота иконостаса в Стефановском приделе, реставрация икон в храме и иконостасе придела Всех Скорбящих Радости, роспись ниш храма. В 1970 году перекрыли крыши и перестроилииконостас в приделе, привели в порядок часовню, осуществили роспись купола. Постепенно Стефано-Пермская церковь вновь приобрела достойный для богослужения вид. До 1991 года в Великом Устюге это был единственный действующий приходской храм.
