Na prostoru današnjeg Perivoja kralja Petra Krešimira IV. prvobitno je, još u razdoblju secesije, bila planirana gradnja nove gradske vijećnice i novog kazališta. U mandatu gradonačelnika Konstantina Graffa vijećnici Slobodnog i kraljevskog grada Osijeka odlučili su da se zbog nedostatka prostora u baroknoj gradskoj vijećnici, smještenoj na glavnom tvrđavskom trgu, treba sagraditi suvremena dovoljno prostrana i monumentalna nova vijećnica koja bi bila u duhu s novim vremenom i koja bi odražavala status ovoga slavnoga grada.

Zbog toga je prostor, veći od 24.000 m2, koji je bio predviđen za izgradnju vijećnice i kazališta još 1913. nazvan Vijećnički trg. Grad je raspisao natječaj za projekte nove kazališne zgrade i nove gradske vijećnice za koje je dao i određene smjernice. Na natječaj su pristigli mnogi projekti, ne smo hrvatskih arhitekata, a i slavni slikar, Osječanin Bela Csikos Sesia, naslikao je skicu za svečani zastor nove kazališne zgrade koja je 1916. godine bila izložena na izložbi Hrvatskih umjetnika u palači Županije. Ostvarenje ovih izvrsnih arhitektonskih i slikarskih ideja poremetilo je izbijanje Prvog svjetskog rata. Nakon završetka rata Osijek se, u novonastaloj državi Kraljevini Slovenaca, Hrvata i Srba, pa Kraljevini Srba, Hrvata i Slovenaca te Kraljevini Jugoslaviji, našao izvan svojih prirodnih prometnih i trgovačkih tokova koje je imao od rimskog doba do raspada Austro-Ugarske Monarhije. Osječani su se sve do 1935. godine, kada je na tom rezerviranom prostoru podignut perivoj, neumorno nadali da će uspjeti sagraditi predviđene reprezentativne gradske institucije.

Za vrijeme gradonačelnika dr. Vjekoslava Hengla ovaj se prostor počeo koristiti, od 1927. do 1932. godine, za odvijanje Osječkog velesajma koji se kontinuirano odvijao, u proljeće i jesen, od 1925. do 1932. godine. Na tome je prostoru 1927. za potrebe Velesajma sagrađen čitav niz izložbenih paviljona od kojih je najveći bio Oktogon, s izložbenom površinom od gotovo tisuću četvornih metara. Osim Oktogona posebnost je bila i Željezna kuća koju je sagradila Osječka ljevaonica željeza i tvornica strojeva d.d. Isticali su se ondje i mali paviljoni Hermana Wirera s pločicama, Matije Klasa s kaljevim pećima, kineski paviljon sa slastičarnicom Krausa i Neumanna, paviljon osječkog Aerokluba koji je osječki graditelj Ante Slaviček projektirao u obliku zrakoplova te mnogi drugi. U pojedinim su se velesajamskim paviljonima na ovom prostoru izlagali prvi modeli automobilskih tvrtki Chevrolet, Chrysler i Ford koji su ovdje imali svoje zastupnike, a bilo je i izloženih aviona, bicikala različitih proizvođača te najnovijih modela traktora, kao i različitih vrsta strojeva najšire namjene. Ovdje su izlagani prvi radioaparati i gramofonske ploče, pisaći strojevi, namještaj, igračke, štapovi za šetnju, krzneni kaputi, odjeća, vina… U sklopu Velesajma bile su predstavljene i brojne osječke tvrtke, od šećerane do lanare, a u jednom od paviljona izlagali su i brojni osječki i drugi hrvatski umjetnici. Zahvaljujući svijesti građana, brojne fotografije te malobrojne diplome, medalje, plakati, katalozi i predmeti koji su bili izloženi na osječkim velesajamskim izložbama pohranjeni su danas u nekoliko zbirki osječkog Muzeja Slavonije, gdje svjedoče o zaboravljenom fenomenu Osječkog velesajma u razdoblju između dva svjetska rata.

Perivoj kralja Petra Krešimira IV., osim što je u prošlosti bio mjesto odvijanja različitih događanja, jednako je tako tijekom povijesti promijenio i nekoliko naziva. Nakon završetka Drugog svjetskog rata iz Vijećničkog je trga preimenovan u Park maršala Tita, da bi nakon uspostave neovisnosti Republike Hrvatske dobio današnje ime. Perivoj je podignut 1935. u stilu francuske vrtne arhitekture koja se odlikuje geometrijskim rasterom staza i simetričnim rasporedom drveća, grmlja i živica te jednako tako oblikovanim rundelama s cvjetnim sadnicama. U vrijeme kada je perivoj nastao krasile su ga i brojne vrste palmi koje su bile posađene u drvene posude, kace, koje su se zimi prenosile u staklenik koji se nalazio u Gradskom vrtu.