Prehistoria Pierwsi ludzie pojawili się w obszarze dolnego Dniestru około 600 000 lat temu. Na obrzeżach dzisiejszej Odessy, w naturalnej jaskini przy ujściu rzeki Kujalnik, paleontolodzy odkryli ślady polowań na niedźwiedzie: broń z kamienia i kości oraz szkielety zwierzęce. Na prawym brzegu ujścia rzeki Chadżybej, w pobliżu wsi Usatowo, odkryto osadę łowców niedźwiedzi z późnego paleolitu (14 tys. – 8 tys. lat p.n.e.). Usatowo jest też stanowiskiem eponimicznym kultury usatowskiej.
Starożytność thumb|left|Olbia, Borysthenes i inne kolonie greckie w północnej części Morza Czarnego, ok. 450 p.n.e. Greccy osadnicy przybywali nad Zatokę Odeską od V do III w. p.n.e. Ich kolonie Olbia i Borysthenes założone zostały na wschód od dzisiejszej Odessy, na wybrzeżu Morza Czarnego. Natomiast na terenie samej Odessy istniało w starożytności kilka małych osad należących do olbijskiego polis. thumb|upright|Odkryte w 2008 r. pozostałości starożytnej greckiej osady oglądać można obecnie na Bulwarze Nadmorskim w Odessie Starogrecka literatura zawiera wzmianki o dwóch z nich: „Havana Isiaka” (przy ujściu rzeki Kujalnik) i „Havana Istrian” (teren dzisiejszego portu). Były to małe wioski z kamienną zabudową, których mieszkańcy uprawiali rolę, zajmowali się rybołówstwem i handlem. Zniszczone zostały w okresie wielkiej wędrówki ludów. Iwan Stempkowski (Иван Алексеевич Стемпковский, 1787 – 1832) i A. Berthe-Delagard – miłośnicy starożytności – badali w XIX w. pozostałości odeskich greckich kolonii, którymi się wtedy żywo interesowano. Niewiele jednak odkryto, gdyż zostały one prawie w całości zniszczone w czasie budowy Odessy na przełomie XVIII i XIX w. W 2008 r. pozostałości jednej z osad starogreckich znajdujących się na terenie dzisiejszej Odessy odkryte zostały podczas remontu Bulwaru Nadmorskiego. Oglądać je tam można obecnie pod przeszklonym zadaszeniem, pod którym eksponowane są fragmenty murów, kawałki amfor itp.
Średniowiecze thumb|Unia polsko-litewska w czasach Jagiełły. Zaznaczone zdobycze Witolda (jasnoróżowym kolorem) i lokalizacja Chadżybeju nad Morzem Czarnym. Na początku XIV w. na włoskich mapach morskich w rejonie dzisiejszej Odessy zaznaczona jest mała genueńska osada-faktoria „Ginestra” znajdująca się na terytorium Ordy Nogajskiej. W 1300 r. chan tej ordy – Nogaj – zabity został na terenie dzisiejszej Odessy w bitwie pod Kujalnikiem. Teren przyłączony został do Złotej Ordy.
W drugiej połowie XIV w. następuje rozpad Złotej Ordy. Na terytorium nadbrzeżnym przy Zatoce Odeskiej osiada Orda Perekopska (Chanat Krymski) na czele z bejem Chadży, zwanym Chadżybejem. W XIV w. Tatarzy wznieśli tu małą warownię Chadżybej. Bej Chadży brał udział w Bitwie nad Sinymi Wodami w 1369 r., w której rozbity został przez Olgierda Giedyminowica.
W wyniku podbojów litewskich pod koniec XIV w., od 1392 r. do końca lat 40. XV w. terytorium między Dniestrem i Dnieprem pozostawało pod władzą Wielkiego Księstwa Litewskiego pozostającego w unii z Polską. Według Jana Długosza, w 1415 r. Władysław Jagiełło wysłał kilka statków z pszenicą z portu o nazwie "Kaczubyeiow"Jan Długosz, Historiae Polonicae, p 367 Cytat: "Wladislaus antem Poloniae Rex, necessitati corum satagens pia commiseratione succurere, petitam frumenti quantitatem dat et largitur, et in portu suo Regio Kaczubyeiow, per cos recepiendam, consignat, Datis autem Alexandre Moldauiae Voieuedae et suae consorti donis reuersalibus, et Anna Regina Cracouiam remissa, processit in Camyeniecz...". Właśnie w tamtym czasie, w roku 1414, do posłowie Jagiełły dotarali na dwór sułtański i Polska nawiązała stosunki dyplomatyczne z Imperium OsmańskimTurcja. Relacje dwustronne, Serwis Rzeczypospolitej Polskiej, gov.pl.
W celu wzmocnienia swej władzy Witold Kiejstutowicz zbudował na brzegu Morza Czarnego fortyfikacje, między innymi rozbudował twierdzę Chadżybej, ulokowaną dokładnie w miejscu dzisiejszej Odessy. Pierwsza wzmianka o jej istnieniu pochodzi z 1415 r., kiedy wymieniana jest przez polskie kroniki. Zamek ten został nadany w 1442 roku przez króla polskiego w dożywocie kasztelanowi i staroście kamienieckiemu Teodorykowi z Buczacza. XVI-wieczny historyk polski Stanisław Sarnicki, pisze że twierdza ta założona została pierwotnie przez Tatarów, którzy nazwali ją na cześć jednego ze swych przywódców. Natomiast podróżnik turecki Evliya Çelebi, który odwiedzał okolice Odessy w XVII w. sugeruje, że po zajęciu przez Turków Akermanu, bogaty człowiek nazywający się Bai zbudował fort na brzegu morskim. Ponieważ odbył on hadżdż (pielgrzymkę) do Mekki otrzymał tytuł chadży, twierdza zaczęła się nazywać Chadżybej (Hadjibai).
W latach 1431–1432 twierdza Chadżybej opisywana jest jako leżąca na ziemiach przyłączonych do Litwy, po konfliktach między królem polskim i wielkim księciem litewskim. W tym czasie ta mała twierdza miała już latarnię morską, wspominaną przez polskie kroniki (wymieniona przez dwa dokumenty z 1442 r.). W okresie tym ziemie wokół Odessy były słabo zaludnione. Większość mieszkańców stanowili koczownicy, natomiast osiadłych rolników było niewielu. Po litewsku tereny te nazywane były Dykra, czyli pustkowie. thumb|Gienadij A. Ładyżenski – Chadżybej (1899)
Epoka nowożytna Panowanie tureckie (XV – XVIII w.) thumb|Od początku XV w. do końca XVIII w. teren dzisiejszej Odessy wchodził w skład Imperium Osmańskiego, które utrzymywało tutaj twierdzę Yeni Dünya („Nowy Świat”) Litwie nie udało się długo utrzymać na tym obszarze. W 1484 r. Turcy osmańscy najechali północno-zachodnie wybrzeże Morza Czarnego i po pokonaniu hospodara mołdawskiego Piotra Raresza zajęli dwa ważne porty: Kilię i Białogród (Akkerman). W efekcie tej wyprawy został zajęty także, sąsiadujący z tymi miastami, Chadżybej. Nowe zdobycze dołączono do sandżaku sylistryjskiego, należącego do wielkiej prowincji Rumelii. W 1538 r. Turcy przeprowadzili reformę administracyjną północno-zachodniego pobrzeża czarnomorskiego. Wydzielono wówczas z sandżaku sylistryjskiego osobny sandżak Akkermanu (Białogrodu), dzielący się na cztery okręgi sądowe (kaza) z ośrodkami administracyjnymi w Akkermanie, Kilii, Benderze oraz w, przejętym z rąk tatarskich, Dżankermanie (Oczakowie). Sandżakbejowi akkermańskiemu podlegało zatem czterech kadich (sędziów religijnych), do których obowiązków należał m.in. nadzór nad podatkami i gospodarką okręgów. Twierdza Chadżybej znajdowała się wtedy w ruinie. W 1578 r. poseł Rzeczypospolitej do chana krymskiego, Marcin Broniewski, widział ruiny „twierdzy chadżybejowej, jakby zapadła się ziemia, omywane szerokim jeziorem znajdującym się niedaleko od morza”. W 1656 r. podróżnik turecki Evliya Çelebi opisywał, że zabudowania tej twierdzy widoczne były jeszcze dosyć dobrze na stromej skale, na brzegu Morza Czarnego. Inżynier francuski G.–L. de Beauplan, który w XVII w. na zlecenie króla polskiego rozbudowywał twierdze na Ukrainie, sporządził mapę tych terenów, na której Chadżebej zaznaczony jest jako ruiny. W 1709 r. szambelan króla szwedzkiego Karola XII, który po klęsce pod Połtawą szukał schronienia w imperium osmańskim, zobaczył na miejscu dzisiejszej Odessy, koło Mielizny Kujalnickiej, „godną pożałowania wioskę tatarską”. W połowie XVIII w. Turcy odbudowali jednak twierdzę Chadżybej, nadając jej nazwę Yeni Dünya (Nowy Świat).
Początki miasta (koniec XVIII w.) W dniu 25 września 1789 r. turecka twierdza Yeni Dünya zdobyta została przez Rosjan pod dowództwem Iwana Gudowicza. Częścią oddziałów dowodził José de Ribas. W walkach brał również udział oddział kozaków pod dowództwem Antona Hołowatego. Z przekazów świadków wiadomo, że w momencie zajęcia przez Rosjan twierdza znajdowała się na wysokim, porosłym skąpymi krzakami brzegu morskim, zajmując teren od dzisiejszego pałacu Woroncowa do połowy Bulwaru Nadmorskiego. Zbudowana była na planie czworoboku obwiedzionego wałem ziemnym. Pośrodku jej stał dom paszy długi na sześć i szeroki na cztery sążnie, obok którego znajdował się głęboki dół służący za magazyn prochu. W czasie pokoju twierdzy broniły cztery armaty. Twierdza nie odgrywała większej roli w tureckim systemie obronnym na północnym wybrzeżu Morza Czarnego. Tuż obok niej położona była osada tatarska, zwana po staremu Chadżybej, składająca się z niedbale zbudowanych kamiennych ziemianek. W przypadku najmniejszego niebezpieczeństwa mieszkańcy osady ładowali swój dobytek na wozy i znikali w stepieК. Смольянинов: Исеория Одессы. Исторический очерк, s. 13.. Na mocy traktatu pokojowego zawartego w Jassach (9 stycznia 1792) tereny te wcielone zostały do Rosji. Od tego czasu część Nowej Rosji. Ukazem Katarzyny II z 27 maja 1794 r. polecono założenie miasta i portu, którym nadana została nazwa Chadżybej (Хаджибей). W styczniu 1795 r. zmieniono nazwę na Odessa. Nazwa tu upamiętniać miała starogrecką osadę Odessos albo Odissos, znajdującą się niegdyś ok. 45 km na wschód od Odessy, na końcu lewego brzegu Tiligulskiego limanu. Oficjalny dokument o zmianie nazwy miasta nie zachował się. Nazwa „Odessa” pojawia się po raz pierwszy w tytule zatwierdzonego przez carycę 10 stycznia 1795 r. wykazu personelu tworzonego właśnie w mieście magazynu soli oraz w ukazie z 27 stycznia 1795 r. o utworzeniu guberni wozniesieńskiejК. Смольянинов: Исеория Одессы. Исторический очерк, s. 22–23.. Po gwałtownym starcie rozbudowy miasta w 1794 r. rozwój Odessy zatrzymany został w czasie panowania syna Katarzyny II, Pawła I (1796 – 1801), który wstrzymał fundusze na budowę i odwołał założycieli miasta: de Ribas i de Volana. Kupcy zaczęli opuszczać miasto, a wiele budynków popadło w ruinę. W 1798 r. miasto otrzymało herb. Z tej okazji przemawiał protojerej Piotr Kunicki. Również w 1798 r. otwarto kolegium magistrackie.
XIX wiek Okres Richelieu (1803–1815) Na mocy ukazu Aleksandra I z 27 stycznia 1803 r. gubernatorem Odessy (градоначальник) zostaje książę Richelieu. Książę przybył do Odessy i objął urząd 9 marca 1803 r. Wiele zrobił dla nowoczesnego urządzenia miasta poprzez budowę nowych ulic, dużych kamiennych budynków, unowocześnienie portu itp. Do dzisiaj zachowały się wspomnienia o księciu Richelieu jako o humaniście i człowieku kulturalnym, co było rzadkością na ówczesnych wyższych posadach państwowych w Rosji. Książę Richelieu pozostał gubernatorem Odessy do 1815 r. Po dymisji francuskiego premiera Talleyranda Ludwik XVIII złożył księciu propozycję utworzenia gabinetu, na co ten w końcu przystał i opuścił Odessę wyjeżdżając do Francji.
Okres de Langerona (1817–1823) W 1815 generał-gubernatorem Nowej Rosji został Alexandre Andrault de Langeron. W 1817 otwarte zostało Liceum im. Richelieu. Zorganizowana przy nim biblioteka stała się później zaczątkiem biblioteki uniwersyteckiej. Również w 1817 Odessa uzyskała status wolnego portu (porto franco), który utrzymała do 1858.
Druga połowa XIX wieku W Odessie, tak samo jak w innych miastach wybrzeża Morza Czarnego rozpoczyna się gwałtowny przyrost ludności. Według oficjalnych danych w 1797 r. w Odessie było 3 tys. mieszkańców. W 1803 było ich już 9 tys., w 1830 – 40 tys., w 1836 – 54 tys. i w końcu w 1856 r. mieszkało tu 104 tys. ludzi. Otwarcie w 1865 drogi żelaznej przyczyniło się znacznie do podniesienia ruchu handlowego i przemysłowego. Kolej otoczyła miasto w kształcie półksiężyca i miała pięć dworców stacyjnych. thumb|Centrum Odessy na przełomie XIX i XX w. Według spisu ludności z 1877 r. Odessa była już czwartym pod względem liczby mieszkańców miastem Imperium Rosyjskiego (po Petersburgu, Moskwie i Warszawie). W granicach administracyjnych miasta mieszkało wtedy 403 532 osób (216 792 mężczyzn i 187 023 kobiety), w obrębie właściwej Odessy łącznie z portem 380 541 osób, z których 45 proc. urodzonych było w Odessie, pozostali zaś przyjechali tu za pracą. Według narodowości (kryterium językowe) w mieście mieszkało 227 425 Rosjan, 124 511 Żydów, 17 395 Polaków, 10 247 Niemców, 5086 Greków, 1137 Francuzów oraz 18 014 przedstawicieli innych narodowościОдесса, история..