Før det 20. århundrede
En meget gammel græsk koloni ved navn Olbia (græsk: Ολβία, herlig) lå måske der, hvor byen ligger nu. Mange monumenter fra gamle tider forbinder dette sted med det østlige Middelhavsområde.
I middelalderen var disse områder en del af Kievan Rus, Galich og Volyn-fyrstendømmet, Den Gyldne Horde, Det Store Litauiske Fyrstedømme, Krim-khanatet og Det Osmanniske Rige. Krimtatarerne drev handel i området i det 14. århundrede. På tidspunktet for de russisk-tyrkiske krige blev landene erobret af Rusland. Det var i slutningen af det 18. århundrede.
Fra 1819 til 1858 var Odesa en frihavn (porto franco). I sovjettiden var det den vigtigste handelshavn i U.S.S.S.R. og en sovjetisk flådebase. Den 1. januar 2000 blev karantænemolen i Odesa handelshavnen gjort til frihavn og fri økonomisk zone i 25 år.
15. århundrede
I det 15. århundrede e.Kr. boede der nomadiske stammer af Nogays under khanatet Krim's regering. Under Khan Haci I Girays regeringstid var han i fare fra Den Gyldne Horde og de osmanniske tyrkere. For at få hjælp gav khanen Odesa til storhertugdømmet Litauen. Det sted, der nu hedder Odesa, blev dengang kaldt Khadjibey (også stavet som Khadjibei, Khadzhibei eller Gadzhibei; litauisk: Chadžibėjus; krimtatarisk og tyrkisk: Hacibey). Det var en del af Dykra-regionen. Der boede kun få mennesker i denne region. De var en del af de turkiske stammer. Landet var for det meste tomme stepper.
Det Osmanniske Rige kontrollerede Khadjibey efter 1529. Den nærliggende region Khadjibey blev kaldt Yedisan. I midten af det 18. århundrede genopbyggede osmannerne en fæstning ved Khadjibey. Den fik navnet Eni Dunia (tyrkisk: Yeni Dünya, bogstaveligt talt "ny verden").
Under krigen mellem Rusland og Tyrkiet (1787-1792) førte Ivan Gudovich den 25. september 1789 en gruppe russiske soldater til Khadjibey. De indtog Khadjibey og Yeni Dünya til det russiske imperium. En spanier i den russiske hær ved navn generalmajor José de Ribas ledede en gruppe soldater. Russerne kaldte ham Osip Mikhailovich Deribas. Hovedgaden i Odesa er i dag opkaldt Deribasovskaya Street efter ham. Tyrkiet lod Rusland beholde byen i Jassy-traktaten (aftalen af Jassy) i 1792. Russerne gjorde den til en del af et sted, som de kaldte Novorossiya (det nye Rusland).
Oprindelse af navnet
I 1794 besluttede den russiske regering at bygge en flådefæstning på ruinerne af Khadjibey-byen. Dette blev byen, der fik navnet Odesa i januar 1795. I det år blev dens nye navn for første gang skrevet med statslige bogstaver. Årsagerne til det nye navn er gået tabt, men folk havde teorier.
Katharina II
Ifølge en af historierne sagde Katarina II, at da nogen sagde, at Odessos skulle være navnet på den nye russiske havn, sagde hun, at alle navne i den sydlige del af imperiet allerede var "maskuline", og at hun ikke ønskede endnu et. Så hun besluttede at ændre det til det mere "feminine" Odesa. Denne historie er muligvis falsk.
Fransk
Der var mindst to byer (Eupatoria og Theodosia) med navne, der lyder "feminine" for en russer; desuden talte Katarina II ikke russisk, da hun var barn, og endelig er alle byer feminine på græsk (og på latin). En anden historie er, at navnet "Odesa" stammer fra et ordspil på fransk. Fransk var dengang det sprog, der blev talt ved det russiske hof. 'Masser af vand' er assez d'eau på fransk. Hvis man siger det baglæns, lyder det som den græske koloni's navn. Ordspil om vand giver mening. Odesa ligger ved siden af et meget stort vandområde, men har kun lidt ferskvand. Under alle omstændigheder er der stadig en forbindelse med navnet på den gamle græske koloni. Så der kan være en vis sandhed i de ting, som folk sagde for længe siden.
Den nye by blev hurtigt en stor succes. Dens tidlige vækst skyldtes i høj grad den indsats, som hertugen af Richelieu gjorde, der var byens guvernør mellem 1803 og 1814. Han var flygtet fra den franske revolution og havde tjent i Katharinas hær mod tyrkerne. Det er hans fortjeneste at have designet byen og tilrettelagt dens faciliteter og infrastruktur. Han anses også for at være en af byens grundlæggere sammen med en anden franskmand, grev Alexandre Langeron, som efterfulgte ham i embedet. Richelieu mindes med en bronzestatue, som blev afsløret i 1828 efter et design af Ivan Martos.
Frihavn
I 1819 blev byen gjort til frihavn, en status, som den beholdt indtil 1859. Den blev hjemsted for en yderst forskelligartet befolkning af ukrainere, russere, jøder, grækere, bulgarere, albanere, armeniere, italienere, franskmænd, tyskere og handlende, der repræsenterede mange andre europæiske nationaliteter (deraf de mange "etniske" navne på bykortet, f.eks. Frantsuszkiy (fransk) og Italianskiy (italiensk) boulevarder, Grecheskaya (græsk), Evreyskaya (jødisk), Arnautskaya (albansk) gader). Byens kosmopolitiske karakter blev dokumenteret af den store russiske digter Alexander Pusjkin, som levede i internt eksil i Odesa mellem 1823 og 1824. I sine breve skrev han, at Odesa var en by, hvor "man kan lugte Europa". Man taler fransk, og der er europæiske aviser og blade at læse".
Odesas vækst blev afbrudt af Krimkrigen i 1853-1856, hvor byen blev bombarderet af britiske og franske flådestyrker. Den kom sig hurtigt, og væksten i handelen gjorde Odesa til Ruslands største korneksporterende havn. I 1866 blev byen forbundet med jernbane med Kiev og Kharkiv samt Iaşi i Rumænien.
Byen blev hjemsted for et stort jødisk samfund i det 19. århundrede. I 1897 blev jøderne anslået til at udgøre ca. 37 % af befolkningen. De blev imidlertid gentagne gange udsat for alvorlig forfølgelse. Der blev gennemført pogromer i 1821, 1859, 1871, 1881 og 1905. Mange jøder flygtede til udlandet, især til Palæstina efter 1882, og byen blev en vigtig base for støtte til zionismen.
Første halvdel af det 20. århundrede
I 1905 var Odesa stedet for et arbejderoprør, der blev støttet af besætningen på det russiske slagskib Potemkin (se også Slagskib Potemkin-oprøret) og Lenins Iskra. Sergei Eisensteins berømte film, The Battleship Potemkin, mindede om opstanden og indeholdt en scene, hvor hundredvis af odesiske borgere blev dræbt på den store stentrappe (nu populært kendt som "Potemkin-trappen"), i en af de mest berømte scener i filmhistorien.
På toppen af trappen, der fører ned til havnen, står en statue af Richelieu. Den egentlige massakre fandt sted i gaderne i nærheden og ikke på selve trappen, men filmen fik mange til at besøge Odesa for at se stedet for "slagtningen". Trappen er fortsat en turistattraktion. Filmen blev lavet på Odesas biograffabrik, et af de ældste biografstudier i det tidligere Sovjetunionen.
Efter den bolsjevikiske revolution i 1917 under Første Verdenskrig blev Odesa besat af flere grupper, herunder den ukrainske Tsentral'na Rada, den franske hær, den røde hær og den hvide hær. Til sidst i 1920 overtog Den Røde Hær kontrollen med Odesa og forenede det med det ukrainske SSR, som senere blev en del af Sovjetunionen.
Befolkningen i Odesa led under en stor hungersnød, der opstod i 1921-1922 som følge af krigen. Rumænske og tyske styrker besatte byen fra 1941 til 1944 under Anden Verdenskrig, hvilket forårsagede alvorlige skader og mange tabte.
Under aksernes besættelse blev omkring 60.000 odenseanere (for det meste jøder) enten massakreret eller deporteret. Mange dele af Odesa blev beskadiget under byens fald og senere generobret i april 1944, da byen endelig blev befriet af den sovjetiske hær. Den var en af de første fire sovjetiske byer, der fik titlen "Helteby" i 1945.
Anden halvdel af det 20. århundrede
I løbet af 1960'erne og 1970'erne voksede byen voldsomt. Mellem 1970'erne og 1990'erne emigrerede størstedelen af Odesas overlevende jøder til Israel, USA og andre vestlige lande. Stor indenlandsk migration af Odesas middel- og overklasse til Moskva og Leningrad, som gav endnu større muligheder for karrierefremgang. Byen voksede dog endnu mere ved at udfylde tomrummet med nye landmigranter fra Ukraine. Industrielle fagfolk blev inviteret fra Rusland og andre sovjetrepublikker.
På trods af at byen var en del af Ukraines socialistiske republik, har den bevaret og i nogen grad styrket sin unikke kosmopolitiske blanding af russisk/ukrainsk/mediterrane kultur. Den har også bevaret sit overvejende russisktalende miljø, hvor der tales en unik russisk dialekt med en unik accent i byen. Byens russiske, ukrainske, græske, armenske, moldoviske, aserbajdsjanske og jødiske samfund har alle bidraget til de forskellige aspekter af Odesa.
I 1991, efter Sovjetunionens sammenbrud, blev byen en del af det nyligt uafhængige Ukraine. I 2020 er Odesa en by med omkring 1,1 millioner indbyggere. Byens industrier omfatter skibsbygning, olieraffinering, kemikalier, metalforarbejdning og fødevareforarbejdning. Byen er også en ukrainsk flådebase og hjemsted for en fiskerflåde. Byen er også kendt for sit store udendørs marked, det syvende kilometer store marked.
Transportnettet i Odesa består af sporvogne, trolleybusser, busser og marshrutkas.