В 1654 году в Вологде свирепствовала эпидемия чумы, называемой в то время моровой язвой. Умерших было так много, что их едва успевали отпевать и погребать. Для укрощения смертоносной стихии вологжане решили построить обыденный, т.е. возведенный за одни сутки, храм. Небольшую деревянную церковь строили всем миром и выполнили обет. С самого основания и во все время построения храма, во всю ночь и во весь день никто из жителей не заразился язвой и с того дня она потеряла свою силу. Мало того, горожане заключили общественный обетный договор, навсегда обеспечивающий существование и благосостояние Спасской церкви.

Церковь упоминал в своих записках дворянин из голландского посольства, проезжавшего через Вологду в 1675 году, Бальтазар Койэтт, охарактеризовав ее как «очень изящную в обычном здесь стиле».

В 1688-1698 годах на месте первоначальной деревянной была выстроена каменная Спасообыденная церковь, в 1896 году переименованная в Спасо-Всеградскую соборную. Во все время существования Спасообыденная церковь была одной из самых высокочтимых церквей города, а по количеству богомольцев, ее посещающих, она относилась к числу первых в городе. Многие вологжане не предпринимали никакого более или менее важного дела без благословения Всещедрого Спасителя, без молитвы перед его чудотворным образом.

Икона Всемилостивого Спаса, также написанная обыденно, считалась главной святыней собора, она слыла чудотворной, хотя известий о чудесах не сохранилось. Икону часто носили по домам.

В XIXвеке приток средств на церковь был так велик, что ее постоянно доделывали и перестраивали, в результате чего в архитектурном отношении она стала довольно неинтересной.

В 1925 году Спасо-Всеградский собор перестроили и превратили в Дом искусств с показом в нем кинофильмов. Позже Дом искусств был переименован в кинотеатр им. Горького.

В 1972 году кинотеатр решили снести. Сделать это удалось только с помощью танков и направленных взрывов. В 1990-х годах на месте, где предположительно располагался алтарь Спасо-Всеградской церкви, был возведен поклонный крест.