История храма восходит к середине XVI века, когда в 1556 году через Вологду проходил крестный ход с Великорецкой иконой святителя Николая Чудотворца. В память об этом событии в городе была построена деревянная церковь во имя Николая Чудотворца, первоначально расположенная на Старом торгу. В начале XVII века церковь была перенесена к Софийскому собору, на территорию, известную как «Известная гора».
В 1698 году деревянная церковь сгорела во время сильного пожара. Каменное здание храма было возведено во второй половине XVIII века, не позднее 1782 года. В 1811 году главный престол был освящён во имя Нерукотворного Образа Господня, а в тёплой трапезной части были устроены приделы: справа — во имя святителя Николая Чудотворца, слева — во имя преподобного Кирилла Новоезерского.
В 1869 году, в память о спасении императора Александра II от покушения в 1866 году, храм был переосвящён во имя святого благоверного князя Александра Невского. В 1860-х годах была проведена реконструкция храма: внутренняя перестройка и замена старой шатровой колокольни на шпилевидную.
В 1910 году, после перевода в Вологду 198-го Александро-Невского пехотного полка, храм стал единственным в городе полковым военным храмом. В 1924 году церковь была закрыта и использовалась под различные нужды: клуб строителей, воинская часть, управление «Главкинопроката», лыжная база. В этот период были утрачены шпиль колокольни и крест над холодным храмом.
В 1978 году церковь была поставлена на государственную охрану как памятник архитектуры регионального значения. В 1980-х годах здание было отреставрировано и передано областному краеведческому музею. В 1997 году храм был возвращён Вологодской епархии. 20 ноября 1997 года была совершена первая литургия, а 6 декабря того же года освящён главный престол.
Архитектурно храм представляет собой кирпичное здание с трёхчастной композицией, симметричной по продольной оси. Основной объём — двухсветный четверик с полукруглой апсидой, увенчанный барабаном в виде двух восьмериков с пилястрами на рёбрах. Купол в виде закрытой урны завершён золотым крестом. К основному зданию примыкает вытянутая трапезная, над западной частью которой возвышается колокольня типа «восьмерик на четверике» с куполом и шпилем. Внешний декор включает сдвоенные пилястры ионического ордера, полуколонки в углах и рамочные наличники с треугольными фронтонами. Главный вход оформлен в виде перспективного портала с арками, утопленными в стену.
В настоящее время храм является воинским и находится на попечении Вологодского казачества. В храме установлена мемориальная доска с именами вологжан, погибших в современных военных конфликтах. При храме действуют воскресная школа и молодёжная театральная студия. Приход оказывает помощь детским домам и интернатам Вологды.
