Парк Победы имеет давнюю и интересную историю. Разные периоды в истории нашей страны отражались на облике территории Парка.

В годы Гражданской войны (1918 – 1920 гг.) и после неё на территории бывшего церковного кладбища Николаевской церкви были похоронены члены Приморско-Ахтарского ревкома и бойцы Красной Армии. Предположительно, с этого времени это место стало называться Братскими могилами, а площадь – Братской площадью.

В 1924 г. над Братской могилой был установлен кирпичный обелиск в виде башенки с надписью «Здесь покоится прах борцов, отдавших свою жизнь за новый строй, имя которому социализм».

В 1920 – 1930-х гг. на Братской площади проводилось празднование 1 мая. На площади находилась парашютная вышка, и молодежь увлекалась прыжками с парашютом.

В 1943 г. после освобождения Приморско-Ахтарского района от немецко-фашистских захватчиков рядом с бойцами Гражданской войны в Братской могиле были похоронены партизаны, казнённые гитлеровцами, и воины Советской Армии, погибшие при освобождении станицы Приморско-Ахтарской. В настоящее время Братская могила является памятником истории регионального значения.

В мае 1965 г. к 20-летию победы в Великой отечественной войне на территории Братской площади над Братскими могилами впервые был зажжён Вечный огонь в память о погибших.

18 мая 1965 г. решением исполкома Приморско-Ахтарского горсовета № 79 Братская площадь была переименована в парк Победы, и на могилах погибших воинов были установлены мемориальные доски.

В 1960-1980-х гг. в парке победы проводились торжественные мероприятия по празднованию Дня Советской Армии и Дня Победы. За несколько дней до 9 мая лучшие пионеры городских школ несли почётный караул у Братских могил и Вечного огня.

За прошедшие годы парк Победы несколько раз реставрировался и менял свой облик. В конце 1980-х гг. в нём были посажены парковые деревья: клёны, липы, каштаны. В начале ХХ века в нём были установлены мемориальные доски в память о погибших в Афганистане, Чечне, при ликвидации аварии на Чернобыльской атомной станции.