Odessa was the site of a 6th century BC Greek trade settlement, possibly established by city of Histria. In the Middle Ages, Odessa was ruled by nomadic tribes of Petchenegs, Cumans, the Golden Horde, the Crimean Khanate, the Grand Duchy of Lithuania, and the Ottoman Empire. The site of present-day Odessa became a fortress known as Khadjibey (named for Hacı I Giray, Kocibey in English). During the reign of Khan Hacı I Giray of Crimea (1441–1466), the Crimean Tatar Khanate was endangered by the Golden Horde and the Ottoman Empire and, and in search of allies, the khan agreed to cede the area to Lithuania. It fell under the control of the Ottoman Empire after 1529.
During the 1760-70s Cossacks took the fortress several times and in 1789 Russian troops defeated the Ottomans and the city of Odessa was founded by Catherine the Great, Russian Empress. The Moldavian colony that later will be known as "Moldavanka" was already there. De Ribas and Franz de Volan recommended the area of Khadzhibei fortress as the site for the region's major port. In 1794 Catherine approved the founding of the new port-city and invested money in construction.
From 1795 to 1814, the population of Odessa increased 15 times and reached 20 thousand people. In the mid-19th century, Odessa became a popular resort among the Russian upper classes. The first city plan was designed by F. Devollan. Colonists of various ethnicities settled mainly in the area of the former Moldavian colony, outside of the official boundaries, and as a consequence, in the first third of the 19th century, it emerged as the dominant settlement. After planning by the official architects who designed buildings in Odessa's central district, such as the Italians Francesco Carlo Boffo and Giovanni Torricelli, Moldovanka was included in the general city plan.
The new city quickly became a major success. Its early growth owed much to the work of the Duc de Richelieu, who served as the city's governor between 1803 and 1814. Having fled the French Revolution, he had served in Catherine's army against the Turks. He is credited with designing the city and organizing its amenities and infrastructure. Richelieu is commemorated by a bronze statue, unveiled in 1828 to a design by Ivan Martos. His contributions to the city are mentioned by Mark Twain in his travelogue Innocents Abroad: "I mention this statue and this stairway because they have their story. Richelieu founded Odessa – watched over it with paternal care – labored with a fertile brain and a wise understanding for its best interests – spent his fortune freely to the same end – endowed it with a sound prosperity, and one which will yet make it one of the great cities of the Old World".
Another Frenchman, Count Andrault de Langeron, succeeded him in office. In 1819, the city became a free port, a status it retained until 1859. It became home to an extremely diverse population of Albanians, Armenians, Azeris, Bulgarians, Crimean Tatars, Frenchmen, Germans (including Mennonites), Greeks, Italians, Jews, Poles, Romanians, Russians, Turks, Ukrainians, and traders representing many other nationalities (hence numerous "ethnic" names on the city's map, for example Frantsuzky (French) and Italiansky (Italian) Boulevards, Grecheskaya (Greek), Yevreyskaya (Jewish), Arnautskaya (Albanian) Streets). Its cosmopolitan nature was documented by the great Russian poet Alexander Pushkin, who lived in internal exile in Odessa between 1823 and 1824. In his letters, he wrote that Odessa was a city where "the air is filled with all Europe, French is spoken and there are European papers and magazines to read".
Odessa's growth was interrupted by the Crimean War of 1853–1856, during which it was bombarded by British and Imperial French naval forces. It soon recovered and the growth in trade made Odessa Russia's largest grain-exporting port. In 1866, the city was linked by rail with Kiev and Kharkiv as well as with Iaşi in Romania. By the early 1900s Odessa had become a large, thriving city, with European architecture and electrified urban transport.
The city became the home of a large Jewish community during the 19th century, and by 1897 Jews were estimated to comprise some 37% of the population. They were, due to interethnic conflict that had existed throughout the 19th century, repeatedly subjected to anti-Jewish backlash. Pogroms were carried out in 1821, 1859, 1871, 1881 and 1905. Many Odessan Jews fled abroad after 1882, particularly to the Ottoman region that became Palestine, and the city became an important base of support for Zionism.
In 1905, Odessa was the site of a workers' uprising supported by the crew of the Russian battleship Potemkin and Lenin's Iskra. Sergei Eisenstein's famous motion picture The Battleship Potemkin commemorated the uprising and included a scene where hundreds of Odessan citizens were murdered on the great stone staircase (now popularly known as the "Potemkin Steps"), in one of the most famous scenes in motion picture history. At the top of the steps, which lead down to the port, stands a statue of the Duc de Richelieu. The actual massacre took place in streets nearby, not on the steps themselves, but the film caused many to visit Odessa to see the site of the "slaughter". The "Odessa Steps" continue to be a tourist attraction in Odessa. The film was made at Odessa's Cinema Factory, one of the oldest cinema studios in the former Soviet Union.
Following the Bolshevik Revolution in 1917 during Ukrainian-Soviet War, Odessa saw two Bolsheviks armed insurgencies, the second of which succeeded in establishing their control over the city; for the following months, the city became a center of the Odessa Soviet Republic. After signing of the Brest-Litovsk Treaty all Bolshevik forces were driven out by the combined armed forces of Central Powers, providing support to the Ukrainian People's Republic. With the end of the World War I and withdrawal of armies of Central Powers, the Soviet forces fought for control over the country with the army of Ukrainian People's Republic. Few months later the city was occupied by the French Army and the Greek Army that supported the Russian White Army in struggle with the Bolsheviks. The Ukrainian general Nikifor Grigoriev who sided with Bolsheviks managed to drive the unwelcome Triple Entente forces out of the city, but Odessa was soon retaken by the Russian White Army. By 1920 the Soviet Red Army managed to overpower both Ukrainian and Russian White Army and secure the city.