A colony from ancient Greece may have once occupied the site of the city. Numerous monuments of antiquity confirm links between this territory and the Eastern Mediterranean. In the Middle Ages these lands were a part of the Kiev Rus, Galich and Volyn Principality, the Golden Horde, the Great Lithuanian Principality, the Crimean Khanate and the Osman Empire. Crimean Tatars traded there in the 14th century. In the course of Russian-Turkish wars these lands were captured by Russia at the end of the 18th century.

Odessa was founded in 1794 by Catherine the Great. In 1764 the Empress formed the territories newly acquired in the south-west other empire into a province called Novorossiya. During the Russian-Turkish war of 1787-91, Don Josef de Ribas, a soldier of fortune born in Naples of Spanish and Irish stock and one of many adventures in Catherine's service, stormed the fortress of Yeny-Dunai at Khadzhibei. De Ribas and his close collaborator, a Dutch engineer named Franz de Volan, recommended Khadzhibei as the site for the region's principal port. Its harbor was deep and nearly ice-free. Breakwaters, on the model of those found at Naples, Livorno and Ancona, could be cheaply constructed and would render the harbor safe even for large fleets. The Governor General of Novorossiya, Prince Platon Zubov — one of Catherine's favorites — gave decisive support to the latter proposal. In 1794, Catherine gave it her approval. She immediately sent twenty-six thousand roubles to de Ribas and de Volan to build a harbor.