Улица Лермонтова сформировалась в конце XVIII – первой половине XIX вв. в соответствии с Высочайше конфирмованным Планом Вологды 1781 года, но первоначально названия не имела. Эта улица впервые фиксируется Планом Вологды 1908 года и Списком жилых домов по состоянию на 22 апреля 1914 года как Александровская. Название дано, по соседнему Александровскому саду, устроенному в 1837-1839 годах в память о посещении Вологды Императором Александром I в 1824 году.
16 октября 1918 года Александровский сад был переименован в Городской сад, а Александровская улица – в улицу Возрождения. 9 мая 1936 года устье Золотухи (между современной улицей Ленина и Пречистенской набережной) было переименовано в улицу Клубную, а 18 апреля 1951 года улицы Возрождения и Клубная были объединены в улицу Лермонтова.
