Celje, mimo katerega je leta 1846 stekla železnica od Dunaja proti Trstu, je v monarhiji slovelo kot prijazno letoviško mestece z lepo, že kar romantično okolico, ki je zlasti v poletnih mesecih nudilo gostom sproščujoč oddih. Zaradi naravnih lepot so ga primerjali s pokrajino ob Renu in ga celo imenovali južni Heidelberg. Dunajskim in graškim Nemcem, ki so tedaj prevladovali med letoviščarji, pa se je mesto zdelo kot biser na Savinji – zaradi kristalno čiste Savinje, okoliških hribčkov z vinogradi in gozdovi, zdravilišč in izvirov termalne vode v okolici, in seveda zaradi mesteca samega, ki je tedaj štelo dobrih 4000 prebivalcev.
Sredi 19. stoletja so Jožefov hrib pogozdili s smrekami. Nato so vzdolž travnika na desni strani Savinje, z ledinskim imenom Vodna glazija, zasadili kostanjeva drevesa, kar predstavlja zametek kasnejšega parka. Kasneje so malo višje ob Savinji zgradili moško in žensko kopališče, preko Savinje pa t. i. promenadno brv, s čimer so park približali mestu. Leta 1971 je bilo ustanovljeno še olepševalno društvo, ki je vsa kasnejša leta med drugim skrbelo za zelena pljuča mesta.