Первое упоминание об этой церкви в исторических источниках, возможно, относится к концу XV в.: в Вологодско-Пермской летописи среди пяти посадских церквей, сгоревших при пожаре 1499 г., упоминается храм Николы (правда, уверенности в том, что речь это могла быть и Николаевская церковь на Верхнем Долу, упраздненная, судя по планам Вологды, в первой четверти XIX века). В писцовой книге Вологды 1627/28 года упоминаются стоящие рядом церкви Николая Чудотворца и Иоанна Златоуста – «обе древяны клецки, а в церквах Божие милосердие образы, и книги, и ризы и на колокольнице колокола и всякое церковное строенье – приходных людей … у церквей служит поп Аверкей Артемьев» (см. список с писцовой книги города Вологды, сделанный в 1629 г., с. 141).
Храм во имя Святителя Николая Чудотворца стоит на высокой надпойменной террасе реки Вологды. Его название – «церковь Николы на Горе» связано с топонимом этой местности. Второе название – «у Золотых Крестов» – объясняют тем, что она находилась поблизости от Горнего Успенского женского монастыря, кресты главного храма которого, возможно, были позолочены. Некоторые краеведы предполагают, что по прошествии многих лет во втором названии Никольской церкви предлог «у» оказался утрачен, и тем самым церковь в народной молве будто бы «приобрела» золотые кресты.
В 1655 г. «посадцкие люди никольския прихоженя, что на Горе», обратились к архиепископу Вологодскому и Великопермскому с необычной просьбой: «Есть де на Вологде на посаде Государево богомолье – ружная церковь Сретения Господня в огороде, мала и ветха гораздо и без паперти, кровля и углы огнили; а поставлена без монастыря [т. е. без ограды], погребения родительского у тое церкви никакого нет и прихожан нет же ни одного двора … , и стоит де та церковь ныне без попа и без пения в пусте», поэтому они просят «пожаловать велеть тое бесприходную и ветхую церковь Сретения Господня перевести со всем строением к церкви к Николе Чудотворцу и к Иоанну Златоусту, к ним, прихожанам, на Гору и велеть бы поставить вново деревянную церковь» (Суворов, с. 108–111). Прихожан Никольской церкви, а в ее приходе тогда насчитывалось всего пять дворов, конечно, интересовали не ветхие постройки Сретенской церкви, а «государево жалованье», которое давалось священникам данной церкви, а также «мост плаучей» «под Ямскою деревнею под Григорьевским на усть реки Тошни», с которого собирался в пользу церкви «мостовой доход» (пошлины). Архиепископ на такой «перенос» дал свое благословение, и была выстроена новая деревянная церковь, имевшая три престола: Николая Чудотворца (главный), Сретения Господня (просуществовал до 1884 г. и был переосвящен в честь Всех святых) и Иоанна Златоуста.
Сведения о дате постройки каменного храма удалось уточнить благодаря рапорту, составленному протопопом Стефаном Иоанновым 1 сентября 1760 г., где есть такие строки: «Церковь каменная Сретения Господня, внизу теплая Николая Чудотворца с приделом иже во святых отца нашего Иоанна Златоустаго, зачата строить наместо деревянной в 1705-м, а окончена и освящена в 1714- м годех» (ВГИАХМЗ. Ф. 2. Оп. 1. Д. 73. Л. 121).
26 января 1930 г. Вологодским горсоветом было принято решение о закрытии Никольской церкви. Это мотивировалось, в частности, тем, что «религиозные общины совершенно не производили никакого ремонта и очень плохо отапливали» здания, что грозило их разрушением. «Забота» о сохранности здания церкви не помешала 6 апреля того же 1930 г. принять решение о его сломе, но, к счастью, этого не произошло. 8 февраля 1930 г. в ходе субботника по «разоружению колоколен» с церкви сняли колокола. Позднее храм использовался под общежитие, а затем под мастерские и гаражи ДОСААФ. В 2008 г. за счет средств областного бюджета на памятнике проведен комплекс противоаварийных работ. В 2015 г. церковь Святителя Николая Чудотворца передана общине верующих Вологодской епархии.
Ныне при храме действует Мро ППх святителя Николая "Золотые кресты" г. Вологды Вологодской Епархии РПЦ МП. Молебны совершаются по особому расписанию. Храм нуждается в стройматериалах и средствах для их приобретения.