Парк был заложен в 1975 году по проекту архитектора И. Е. Фиалко. Событие посвящалось празднованию 30-летия Победы в Великой Отечественной войне. Мероприятия по его созданию носили коллективный характер. Участие в обустройстве принимали сотрудники садово-парковых учреждений, а также прочие городские трудовые коллективы, моряки, учащиеся средне-технических, высших учебных заведений и школьники.

Основой планировки стала идея озеленения обособленных аллей, посвящённых памяти городов-героев СССР. Планировка территории подразумевала создание несколько участков, символизирующих определённые города. Двадцать девятого октября 1977 года произошла закладка аллей одиннадцати городов. На каждой производилась посадка конкретных деревьев, произрастающих в соответствующих климатических зонах:

• Московская аллея — ели и березы;

• Ленинградская аллея — липы;

• Киевская аллея — каштаны;

• Севастопольская аллея — ленкоранские акации;

• Одесская аллея — белые акации;

• Тульская аллея — березы;

• Новороссийская и Керченская аллеи — орехи;

• Брестская аллея — вязы;

• Минская аллея — ивы;

• Волгоградская аллея — тополя.

1983 год — Школа водолазов г. Севастополя закладывает дополнительный участок, посвященный её столетию. Позднее, в этом же году появилась аллея Олимпийцев, созданная Олимпийской советской сборной в честь выдающихся достижений СССР в спорте.

В дальнейшем Парк Победы неуклонно развивался, на территории появлялись новые памятные участки:

• Центральная и Комсомольская аллеи;

• аллеи Медиков, Воинов Афганистана, двухсотлетия города;

• рощи Партизан-подпольщиков, 200-летия Черноморского флота и Гидрографической службы ЧФ;

• участок Героев бронепоезда «Матрос Железняков».

Сегодня дорожки вымощены плиткой, на аллеях размещено свыше ста пятидесяти скамеек, порядка 150 фонарей с плафонами из противоударного стекла, оборудованы беседки. В Парке Победы сохранились старые растения. Платаны, тополя, клёны, сосны, можжевельники, голубые ели, кипарисы, лаванда, розмарин — здесь можно увидеть различных представителей растительного мира.

9 мая 2019 года парк Победы открылся после реконструкции. Была обновлена центральная аллея, установлены 15 новых фонтанов: фонтан «Победа» у входа в парк в виде 5-и конечной звезды советского ордена «Победа», фонтан «Центральный», а также 13 фонтанов у звёзд городов-героев.