Улица Авксентьевского сформировалась в конце XVIII – первой половине XIX вв. в соответствии с Высочайше конфирмованным Планом г. Вологды 1781 года. Первоначально называлась Ехаловы Кузнецы (название впервые фиксируется Планом Вологды 1824 года).
Название восходит к улице Ехаловы Кузнецы, фиксируемой Переписной книгой г. Вологды 1711-1712 годов. Название сохраняется ещё на Плане Вологды 1908 года. Однако, в списке жилых домов по состоянию на 22 апреля 1914 года улица называется Кузнецкой. 23 октября 1963 года улица Кузнецкая была переименована в улицу имени К.А. Авксентьевского – «губвоенкома, командующего 4-й армией и войсками Средне-Азиатского и Закавказского военных округов, боевого соратника М.В. Фрунзе».