Pargi rajamine
Turu asemele planeeriti haljasala, mille autoriks aia- ja pargikujundaja Harald Heinsaar (1912-1960). 16.oktoobri park rajati 1947 – 1950, samaaegselt Estonia rekonstrueerimisega.
Teatri- ja kontserdisaali ümbruse haljastusprojekti autor sai 1950.a. Nõukogude Eesti Preemia. Teatrihoone põhja- ja idafassaadi ümber jäeti avarad sõiduteed. Teatri põhjafassaadi ette pargialale jäeti alles 1931.a. paigaldatud 1905.a. monument. Vaadeldav pargiosa oli lihtsa planeeringuga, vaid haljasala, puud ja pargipingid. Läbi pargi kulgesid suhteliselt laiad liikumisteed. Pargialale hooneid ega paviljone esialgu ei rajatud.
1959.a. planeeriti pargi läänepoolne ala osaliselt ümber seoses uue 1905.a. monumendi paigaldamisega haljasala keskele.
Monumendi alus viidi madalamale.
Pidulikum, keerulisema planeeringuga pargiosa jäi teatrist ida poole Pärnu maantee ja Estonia puiestee vahele. Selle keskel asus ringikujuline ala, mille keskmesse oli ette nähtud purskkaev. Purskkaevu siiski ei teostatud, seda asendas lilleklump koos dekoratiivvaasiga ning istepingid selle ümber. Selles pargiosas loodi tasapindade eri kõrgusega intiimsem istepinkidega puhkesaareke.
Endise turuhoone vundamendid jäid parki alles, nende keskele maa alla rajati teatrile vajalik veereservuaar, mis on tänaseks kaotanud tähtsuse.
Samaaegselt Estonia ja pargiala taastamisega toimus Tallinna esimese generaalplaani koostamine. Sellega tegeles arhitektide kollektiiv H.Armani, O.Keppe ja A.Soansi juhtimisel. Ka Viru väljaku planeerimise võistlus. See puudutas ka osaliselt pargiala, mis jäi Viru tänava pikendusest väljaku poole. Sellele alale (Mere puiestee teljele) planeeriti 1950. aastate algul nii Stalini monumenti kui ka Võidu monumenti (vaata Keskväljaku makett).
1972. aastal valmis endise Vene turu ja osaliselt Kalevi aia alal Viru hotell (arhitektid H.Sepman ja M.Port). 1976. aastal parki uuendati ja 1978. aastal paigutati selle keskossa Anton Hansen Tammsaare kuju (autorid skulptor Jaak Soans ja arhitekt Rein Luup).
2006. aastal toodi Viru hotelli juurde parki (enne asus basseinide alal) Edgar Viiese skulptuur “Merineid“, mis on pühendatud XXII olümpiamängude Tallinna purjeregatile.