W 1846 roku powstał nowy plan regulacji zagospodarowania terenów dawnych fortyfikacji napoleońskich w związku z budową mostu Kierbedzia. Plan ten oparty na wcześniejszym opracowanym w 1835 przez Jakuba Łaszyńskiego pozwolił na wytyczenie obszaru parku Praskiego, a także m.in. ulic Szerokiej (obecnej ks. Ignacego Kłopotowskiego), Brukowej (obecnie Stefana Okrzei) i Jagiellońskiej. 4 kwietnia 1865 car Aleksander II wydał specjalny ukaz zezwalający na powstanie parku, który został nazwany na jego cześć parkiem Aleksandrowskim. Był to pierwszy publiczny park miejski na Pradze.
Park powstał na podmokłym terenie esplanady fortu Śliwickiego, dawnego koryta Wisły i krótkich uliczek Golędzinowa, zabudowanych drewnianymi domami. Prace nad jego założeniem były prowadzone w latach 1865–1871 według projektu Jana Dobrowolskiego (kierownika Ogrodu Krasińskich, a potem Ogrodu Saskiego). Park został zaprojektowany w stylu geometryczno-krajobrazowym. Osią założenia była szeroka aleja wychodząca z obecnego placu Weteranów 1863 roku i biegnąca przez cały park w kierunku północno-zachodnim. Został on otwarty dla publiczności w roku 1871. Posiadał wiele urządzeń służących rozrywce odwiedzających;