Парк Победы был торжественно открыт 7 мая 2005 года, в канун праздника — 60-летия Великой Победы. Закладка парка началась еще в 1984 году на захламленном пустыре между улицами Ворошилова и Красной. В 1986 году проект парка получил одобрение областного градостроительного совета и совета директоров города. Был вывезен мусор, сделана планировка, посажены деревья. Затем появилась ограда, была оборудована спортивная площадка. И только в 2005 году установлены памятные плиты в честь городов-героев и каменчан — Героев Советского Союза, а в центре — стела «Звезда». В Парке Победы города установлены мемориальные плиты Героям Советского Союза, родившимся и жившим в Каменском районе: • Андреенко Евгений Георгиевич (1917–1982). • Блинов Никита Павлович (1914–1942). • Величко Геннадий Иосифович (1922–1999). • Данилов Василий Александрович (род. 1924). • Ковалёв Андрей Матвеевич (1916–2002). • Корниенко Иван Михеевич (1917–1948). • Косоногов Лев Васильевич (1904–1943). • Котов Яков Михайлович (1921–1990). • Найдёнов Григорий Артёмович (1915–2010). • Радиловский Семён Ефимович (1922–1998). • Тимощенко Александр Григорьевич (1903–1978). • Тупикин Григорий Васильевич (1916–1965). • Фесин Иван Иванович (1904–1991). • Фёдоров Иван Евграфович (1914–2011). 7 сентября 2012 года здесь состоялось торжественное открытие мемориального знака в честь уроженца Каменска, Героя Советского Союза лётчика Ивана Евграфовича Фёдорова.