[8] It is believed by some historians that Oleshia existed from the 10th to the 13th century as a large Slavic trading city, which was a stronghold of Kievan Rus in the lower Dnieper.

[8] In the mid-15th century, Oleshia was destroyed by the Ottoman Empire, who established Ochakiv nearby as a post to control the Dnieper River.

[8] From the 15th to 18th century, the territory of modern Oleshky was under the control of the Crimean Khanate, who permitted the Zaporozhian Cossacks to settle there.

Due to this as well as Oleshky's status as uyezd center, contributed to rapid growth of the small town during the early 19th century.

The population grew rapidly again during the Crimean War in 1853–1856, when Oleshky became a supply point for the Russian army, and troops passed through the town on their way to defend Sevastopol.

At the end of the war, Oleshky finally fell under control of the Bolsheviks, who established the communist Soviet Union on much of the former territory of the Russian Empire.

[11] After transferring it repeatedly between different short-lived administrative divisions between 1920 and 1944, Oleshky was eventually subordinated to Kherson Oblast of Soviet Ukraine.

[12] According to Soviet sources, a total of 2,160 civilians in Oleshky and neighboring localities were murdered by the Nazis, and 356 were deported to Germany for forced labor.

[14] It was not until 19 May 2016 that the Verkhovna Rada (Ukraine's national parliament) adopted the resolution to rename Tsiurupynsk as Oleshky and conform to the law prohibiting names of Communist origin after a 9-year campaign by the town's council and residents.

[20][21] 7 months later, Russian forces withdrew from Kherson city and the part of the region north of the Dnipro river in November 2022.

[23] On 20 March 2023, the Russian occupiers reinstated the name "Tsiurupynsk" for the town; the reason given was that it was "part of the reversal of the renamings" that had taken place after the 2014 Revolution of Dignity, which they referred to as "the coup d'état in Kyiv.

"[11] In June 2023, Oleshky was almost completely flooded as a result of the destruction of the Kakhovka Dam, with the water rising to roof level for many buildings.