Денисовський (до 1880 р.), Олександрівський (1880—1927 рр.), Тарасо-Шевченківський (1927—1939 рр.), імені Леніна (1939—2014 рр.), Міський (2014—2016 рр.)
Олександрівський парк знаходився між містом і фортецею, займаючи велику на той час площу. Вперше парк на цьому місці заклали у 1785 році за розпорядженням Г. О. Потьомкіна, але із занепадом Херсонапарк був занедбаний, а дерева вирубані.
У першій половині XIX століття на його території влаштували плац-парадну площу, і до 1868 року тут проводились кінні перегони. У 1869 році віце-губернатор Денис Гаврилович Карнович ухвалив рішення відновити парк і розпорядився висадити тут дерева. Пізніше, коли парк перейшов у відання міського управління, висадка дерев була закінчена і парк отримав назву Денисовський в честь свого засновника.
У 1880 році в пам'ять 25-річчя царюванняімператораОлександра II парк перейменували на Олександрівський. Тут завжди була публіка, особливо по вихідних. Перш за все тому, що головна діагональна алея зручно пов'язувала район Військового форштадта і фортеці з головною вулицею міста Суворовською. У 1897 році міщанин Володимир Матаков побудував у парку альтанку, в якій торгував соками та водами. Рівно через десять років він замінив альтанку дерев'яним павільйоном. У вересні 1897 року був затверджений проєкт А. І. Сварика на будівництво в Олександрівському парку дерев'яних будинків для естради, сцени і буфету.
Парк мав регулярне променеве планування, що було незвичним для Херсона. Судячи з представленого проєкту, його автори прагнули до пейзажного (англійського) типу планування, де прямі алеї чергувалися з кривими стежками, лінійні посадки — з вільно згрупованими деревами. Важливо відзначити і відсутність ключового об'єкту парку — дуба в центрі. Мабуть, до регулярності (французькому типу) проєктувальники прийшли трохи згодом, в процесі облаштування парку, ймовірно, після того, як був посаджений знаменитий черешчатий дуб, який треба було планувально виділити. Від дуба, оточеного огорожею, врізнобіч розійшлися вісім прямих алей.
У 1927 році Олександрівський парк було перейменовано в Тарасо-Шевченківський, а в 1939 році він отримав назву «Парк культури і відпочинку ім. Леніна». 30 жовтня 2014 року Херсонська міська рада ухвалила рішення про надання парку назви «Міський парк»[2]. У 2016 році парк перейменовано на Шевченківський[3].
