Николаевский храм во Владычной слободе был восьмым каменным храмом города, но поскольку церкви Иоанна Предтечи и Знамения Божией Матери в Дюдиковой пустыни, храмы Свято-Духова монастыря и Кирилло-Иоанно-Богословская Семинарская церковь на Соляном дворе, имеющие более раннее происхождение, до настоящего времени не сохранились, это храм становится третьим по древности после Софийского собора и холодной церкви Димитрия Прилуцкого на Наволоке, не считая также храмов Спасо-Прилуцкого монастыря, вошедшего в черту города в 1993 году.
В 1781 году приход Николаевского храма был третьим по величине в Вологде и включал в себя 72 двора. В 1892 году он занимал уже второе место в городе с численностью прихожан 847 человек.
В феврале 1930 года храм закрыли, колокола сняли. Первоначально в нём поселили высланных из средней и южной части СССР «кулаков», затем в здании храма, лишившегося купольного завершения, действовал завод игрушек и валенная фабрика. В начале 1990-х годов при церкви была создана община, постепенно начался сбор средств на восстановление храма. Во время реставрации церкви Николая Чудотворца были установлены новые купола, появилась новая кирпичная кладка внутри помещения.
Сегодня в Николо-Владычненском храме покоятся мощи Святителя Антония, епископа Вологодского и Великопермского, перенесённые из Софийского собора 26 сентября 1998 года.
Храм выделяется среди созданных в то же время в Вологде аналогов большими размерами, пятью световыми барабанами и двустолпным строением. В остальных чертах, высокий подклет, внешний декор, двухапсидность, перестроенная в XVIII веке колокольня, церковь Николая во Владычной слободе, типичный для Вологды посадский храм второй половины XVII века.
Г. К. Лукомский так описывал храм: «Церковь св. Николая во Владычной слободе представляет собою очень высокий куб, увенчанный пятью, тесно и красиво по композиции поставленными, куполами. Хороши формы блестящих, упругих, луковичных глав, барабаны убраны, как и в Иоанновской церкви в Дюдиковой пустыни, арочным поясом, поддерживающимся колонками, перехваченными по середине гирьками». В деталях обработки фасадов куба заметно стремление к декоративизму, выраженное особенно ярко в больших закомарах, отделенных от стен карнизом. Здесь ещё в начале XX века находились живописные клейма с изображением двунадесятых праздников. Стенной живописью были также украшены всходы в верхний храм. Примыкающая к церкви с западной стороны трапезная связывает храм с изящной ярусной колокольней, выстроенной в середине XVIII века. Её стройный изящный столп состоит из четверика, высокого восьмигранного яруса со звоном и двух небольших, поставленных друг на друга восьмериков, завершенных главкой. Подобные ярусные колокольни, пришедшие в XVIII веке на смену древнерусским шатровым, были весьма характерны для архитектуры Вологды, а также других северных городов России того времени. Самый тяжёлый колокол на колокольне весом 2 тонны отлил в 1782 году в Москве мастер Асан Струговщиков.
Интересна алтарная часть подклетного этажа, сильно выдающаяся к востоку и заканчивающаяся двумя полукружиями апсид, приём, встречающийся в ряде вологодских храмов, церкви Константина и Елены, тёплая Димитрия Прилуцкого, Успения Божией Матери.
Интерьер Никольского храма был выполнен в стиле барокко. Стенную роспись заменяла богатая орнаментальная лепка, покрывавшая своды, арки и столбы. В церкви имелся иконостас в стиле Людовика XVI, сочетавший в себе живопись, скульптуру и деревянную резьбу.
