Здание храма представляет собой двусветный четверик, увенчанный двумя рядами декоративных кокошников и пятью луковичными главками, с трёхчастным алтарём, двухпридельной трапезной, примыкает с запада, и трёхъярусной шатровой колокольней. В основании шатра, пояс расположенных в шахматном порядке кокошников, и двойной фриз из изразцов, сам шатёр пронизан рядами декорированных отверстий для выпуска звуковой волны и предохранения шатра от трещин. На колокольне было шесть колоколов. Кресты кованые, ажурные, на нижней перекладине центрального креста можно рассмотреть год установки 1783 год. На четырёхскатной кровле, пять барабанов с луковичными главами, центральный барабан световой, остальные ложные. Низкий трехапсидный алтарь с высокой барочной кровлей колоколообразной формы увенчан маленькой главкой.
Приделы, Андреевский, Димитриевский, Екатерининский и Сретенский. В интерьере сохранились остатки живописи с пышной лепниной в стиле барокко.
Церковь освящена в 1723 году. В XVIII—XIX веках поновлялась. В 1753 году в церкви произошёл сильный пожар, внутреннее убранство и иконостас были безвозвратно утрачены. В 1755 году церковь была отремонтирована, получив нынешний вид.
В 1930-х годах церковь была закрыта и использовалась под различные хозяйственные нужды, была занята спортзалом, находилась в ведении музея. С 1988 года по начало 1990-х на ремонте церкви работал отряд «РеставросЪ», занимавшийся отведением грунтовых вод от фундамента, восстановлением оконных проёмов, кованых решёток, каменного декора, были заменены обветшавшие изразцы и т.д.
В 2011—2012 годах в рамках подготовки к юбилею города был проведён большой комплекс ремонтно-реставрационных работ, финансируемых за счёт федерального бюджета, были расчищены и отштукатурены стены, при этом лепнина и фрагменты оригинальных фресок сохранены. В августе 2012 года архиепископ Вологодский и Великоустюжский Максимилиан отслужил в церкви Спаса Всемилостивого первый после реставрации молебен.
