С середины XIX века и до начала 30-х годов ХХ века она называлась Нахичеванской. Затем носила имя Коллонтай, а в 1945-м была переименована в улицу Победы.

Нахичеванской её назвали в честь делегации из города Нахичевань-на-Дону (сейчас – один из районов Ростова-на-Дону), присутствовавшей на открытии Ейска в 1848 году.

В дальнейшем представители армянской диаспоры оставили заметный след в истории города как предприниматели и благотворители.

Когда-то часть улицы занимал Гостиный двор, где располагались его 4-5 ряды. Торговали, в том числе и оптом: мукой, зерном, а также здесь располагались хлебные ссыпки (склады).