Historie Vítkova sahá až do dob Karla IV., kdy svahy tohoto vrchu byly využívány k vysazování vinic. Mnohé z nich v té době patřily měšťanovi Vítkovi z Hory, po kterém vrch dostal svůj název, který se s některými pauzami zachoval doposud. Nicméně primární známost si toto místo získalo slavným vítězstvím Žižkova vojska nad vojskem krále Zikmunda, které se odehrálo v roce 1420. Následně však veškeré vinice byly zdevastovány a zůstaly opuštěné až do 90. let 19. století, kdy se poprvé začalo uvažovat o přeměně neupraveného vrchu na městský sad. Tyto plány byly později přerušeny První světovou válkou.

Důležitým milníkem bylo bez pochyby vybudování památníku v letech 1929—1938 na počest československých legionářů. Právě tehdy park prošel svými doposud největšími úpravami.

Po Druhé světové válce byla odhalena i signifikantní bronzová socha Jana Žižky, která v současnosti patří mezi první desítku největších jezdeckých soch na světě. Následně místo sloužilo jak mauzoleum Klementa Gottwalda a jiných komunistických činitelů, avšak později v 90. letech byly některé jejich ostatky předány rodinám či pohřbeny na Olšanských hřbitovech.