Улица сформировалась в конце XVIII – первой половине XIX вв. в соответствии с Высочайше конфирмованным Планом Вологды 1781 года. Первоначально представляла собой две улицы (названия которых впервые фиксируются Планом Вологды 1824 года): Калашная (от слова «калач») и Владычная Слобода. Последняя получила название, так как проходила по территории пригородной слободы, до 1649 года принадлежавшей Вологодскому архиерейскому дому.
23 мая 1935 года улица Владычная Слобода была переименована в улицу Героев Авиации «в знак памяти о героях авиации – экипажа погибшего самолёта «Максим Горький» и ударников ЦАГИ».
18 апреля 1951 года улица Героев Авиации была присоединена к улице Калашной, впоследствии переименованной в улицу Гоголя.