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