Церковь Св. Николая начала строиться в 1713 году. До этого времени на этом месте стояла деревянная церковь, год постройки которой неизвестен. Однако сохранились документы, указывающие на то, что церковь существовала уже в самом начале XVII века. В Вологодских Епархиальных ведомостях за 1865 год указано следующее: «прежняя деревянная церковь писалась такъ: въ 1626 г. « Церковь на площади, Нерукотворный образъ Спасовъ», въ 1639 г. «Церковь Всемилостиваго Спаса на Старой площади» и въ 1668 г. «Храм Николая Чудотворца, на Старой площади...». Впоследствии Старая площадь стала именоваться Сенной. В 1713 году деревянную церковь снесли, и на ее месте было начато строительство каменного храма. Построили фундамент и стены, а затем строительство прекратили в связи с указом Петра I, запрещавшим строить что бы то ни было в провинции. Каменных дел мастеров отправили в Петербург. По этой причине церковь длительное время оставалась недостроенной, и достроили ее только в 1777 году.

Храм Святого Николая Чудотворца на Сенной площади, построенный в классическом стиле XVIII столетия, был одним из красивейших храмов Вологды. В книге Г.К. Лукомского при описании храма Св. Николая на Сенной площади отмечено: «...Стены церкви убраны пилястрами; надъ окнами украшения, розетки, маскароны – руки очень хорошего мастера. Закрашенная въ теплый, бледно-оранжевый тонъ, церковь производить чрезвычайно художественное впечатление. Красивъ и ея общий силуэтъ, великолепно выисканы все пропорции (портик), отличны и детали...». Церковь снесена в 1929 году.