Перемога - повний успіх у бою, остаточна поразка військ противника. Рішенням сесії міської ради від 08.05.1985 року частина вулиці Богдана Хмельницького від вул. Першотравневої (нині Університетська) до вул. 1905 року (нині Полковника Гегечкорі) була перейменована на честь Дня Перемоги - дня остаточної поразки нацистської Німеччини у Другій світовій війні - і отримала назву "вулиця Перемоги". Площа Перемоги одержала своє ім'я набагато раніше - на першому післявоєнному плані відбудови Кременчука 1954 року ця назва вже була.
Назва історична. На карті Кременчука 1901 року вже була позначена. Названа на честь міста Переяслава або, можливо, на честь Переяславської ради 1654 року.
Пилип Орлик - український політичний, державний і військовий діяч, Генеральний писар (1702-1709), гетьман Війська Запорозького у вигнанні (1710-1742), поет, публіцист. Основними пріоритетами зовнішньої політики Пилип Орлик уважав: необхідність шведської протекції з гарантією незалежності й територіальної цілісності України, встановлення міцного миру та військового союзу з Кримським ханством. У 1710 році Пилип Орлик уклав зі старшиною та запорожцями «Договори і Постановлення Прав і вольностей Війська Запорозького» — документ, який пізніше дістав назву Конституція Пилипа Орлика — так звана «Бендерська конституція». Нею він зобов'язався обмежити гетьманські прерогативи, зменшити соціальну експлуатацію, зберегти особливий статус запорожців і боротися за політичне й церковне відокремлення України від Московії. Створення цих документів вважається значною заслугою Пилипа Орлика в історії України. Росія намагалася переконати увесь світ в тому, що України, як держави ніколи не існувало. Проте ще у 1710 році українець, гетьман Пилип Орлик створив першу в Європі модель вільної, незалежної держави. Це Конституція Пилипа Орлика, в якій було прописано поняття «вільного народу», основи демократії та правосуддя, антикорупційні та соціальні засади.
Оксанченко Олександр Якович – народився 26 квітня 1968 р. в с. Маломихайлівка Покровського району Дніпропетровської області. Український військовий льотчик I класу, заступник командира з льотної підготовки 831 бригади тактичної авіації повітряного командування «Центр» Повітряних Сил ЗСУ, полковник запасу, учасник АТО. Почесний громадянин м. Миргорода. Льотчик-ас, воїн російсько-української війни. Життя пов’язане з Полтавщиною. З нього та з тих кого він навчав створений образ Привид Києва. Це пілот який отримав нагороду - «Найкращий пілотаж серед країн-партнерів НАТО» у Великій Британії. Нагороджений орденом Данила Галицького. Полковник Оксанченко загинув 25 лютого 2022 року у повітряному бою під Київом, відволікаючи на себе ворожу авіацію. 28 лютого 2022 року полковник Олександр Якович Оксанченко посмертно удостоєний звання Герой України та ордена "Золота Зірка". З 2022 року вулиця Аерофлотська носить назву «Вулиця Полковника Оксанченка».
Правобережна - названа за місцем знаходження вулиці у правобережній частині Кременчука. Жодних історичних коренів не має. З 2016 р. провулок Червоноармійський називається "провулок Правобережний"(Рішення Кременчуцької міської ради Полтавської області VII скликання від 16 лютого 2016 року).
