Дата основания церкви неизвестна. Идентификация первого упоминания затруднена ввиду существовавшей относительно недалеко церкви Николая Чудотворца на Верхнем Долу и церкви, затем, придела Николая Чудотворца в близлежащем Горнем монастыре. В целом, в районе Ленивой площадки в средневековой Вологде находилось несколько церквей на небольшом расстоянии друг от друга.
Н. В. Фалин, ссылаясь на сотную грамоту 1627 года, указывает, что на месте современной церкви Николая «Золотые Кресты» вероятно находились «церковь Николы Чудотворца, другая церковь Ивана Златоустаго».
Считается, что топоним «Золотые Кресты» перешёл к церкви в XVIII веке, в 1701 году церковь упоминается ещё как «Николая Чюдотворца на горе». Первоначально «Золотыми Крестами» называли Успенский собор Горнего монастыря. Так в сообщении Городского магистрата 1782 года Николаевская церковь названа «у Золотых Крестов». После пожара 1761 года своды и главы Успенского собора были значительно повреждены, утратив позолоту. После этого название перешло к Никольской церкви, которая стала именоваться Никола на Горе — «Золотые Кресты». «Никол. у Золотых крестов» названа церковь в книге И. К. Степановского 1890 года. Храм закрыт в 1930 году, занят общежитием, затем автомастерской и гаражами ДОСААФ. На 2011 год церковь пустует, интерьеры уничтожены, выбиты окна, глава и завершение колокольни разрушены, колокола сняты, кровля разрушается.
Кирпичный двухэтажный храм, состоит из высокого стройного четверика, короткой трапезной и колокольни. Верхний храм, двусветный, с богатыми наличниками в форме петушиных гребней во втором ярусе и более простыми, треугольной формы, фронтончиками в третьем ярусе, все сбиты, вероятно, во время перестройки XIX века. Четырёхскатная кровля покрывает один ряд небольших кокошников. Главка одна, хотя высказывается предположение, что исходно их могло быть пять. Колокольня в стиле классицизма сооружена в первой трети XIX века. Первые два яруса колокольни имеют форму четвериков, при этом оформление второго яруса очень необычно, в центре каждой из боковых стен помещена ниша, окружённая лучеобразной рустовкой, в нише находится ваза. Ярус звона цилиндрический, декорированный соответственно углам четверика спаренными колоннами тосканского ордера.
Помимо главного престола Николая Чудотворца, в храме были освящены Трёхсвятский, Всехсвятский, Введенский и Кирилло-Новоезерский приделы. Алтарная часть — двухапсидная, что нехарактерно в целом для русской, но распространено в вологодской архитектуре.
Петербургский искусствовед и архитектурный критик Г. К. Лукомский в начале XX века так описывает интерьеры храма, «Над входом в церковь — старинная икона в серебряном окладе. Хорош иконостас — из двух полукружий. В верхней церкви прелестный иконостас с колонками и с высокими фронтончиками поверху. Но ужасны все фрески в церкви. Паникадило прекрасное, не старинное, но отличного рисунка».
