Redan i gamla tider fanns bebyggelse i detta område. Stadens moderna historia började då turkarna grundade fästningen Khadjbej på 1300-talet. En tatarbosättning är omtalad 1415.[8] Området var en del av Polsk-litauiska samväldet och från år 1764 en del av Osmanska riket.[5][6]
Några år senare, 1791, blev området en del av det ryska kejsardömet, då under namnet Chadzjibej (ry. Хаджибей).[4] En hamnstad började byggas 1794[4] på land som 1789 annekterats av Kejsardömet Ryssland från Osmanska riket. Staden fick året därpå, 1795, sitt nuvarande namn, Odessa.[4] Namnet hämtades från den forntida grekiska kolonin Odessos. Under guvernören Armand Emmanuel du Plessis de Richelieu, senare fransk statsminister, uppfördes här en stad, som 1814 hade 35 000 invånare.[9]
Staden fortsatte att växa snabbt, särskilt under åren 1817–1859 då Odessa var frihamn, och dess betydelse ökade genom den 1866 anlagda järnvägen till Kiev och Charkiv. År 1852 fanns här 97 000 invånare och 1900 449 673. I takt med industrialiseringen av staden växte särskilt en stor fattig arbetarbefolkning fram i staden. 1865 fick staden ett universitet.[4]
I samband med Ryska revolutionen 1905 utbröt våldsamma strider i Odessa, och befolkningen minskade med 80 000, men var 1912 åter uppe i 631 040. Efter Kerenskijregimens fall 1917 var Odessa länge en härd för kontrarevolutionära trupper och utländska invasionstrupper. Först i början av februari 1920 lyckades Röda armén ta kontrollen över staden, vars befolkning då sjunkit till 314 480.[10]
Odessas bebyggelse skadades svårt under andra världskriget.[8] Efter belägringen av Odessa utplånades större delen av den judiska befolkningen i Odessamassakern den 22–24 oktober 1941 av tyska och rumänska styrkor, hjälpta av ukrainska medlöpare. 30 000 människor mördades i massakern.[11] Mellan 1941-1944 ockuperades staden av rumänska trupper, för att i april 1944 återtas av Röda armén.[4]
Den 25 januari 2023 utsågs Odessas historiska centrum till världsarv av Unesco.[12]
Odessa ligger vid Svarta havet några kilometer öster om floden Dnestrs utlopp.
Odessa, med drygt 1 miljon invånare, är Ukrainas tredje största stad och landets viktigaste handelsstad. Staden är också den största vid Svarta havet. Odessa var Kejsardömet Rysslands tredje största stad efter Moskva och S:t Petersburg.
Odessa var den första staden i Kejsardömet Ryssland som fick ångdrivna spårvagnslinjer (1881), bara ett år efter de första hästspårvägarna. Spårvagnstrafiken drevs av ett belgiskt företag. Odessa fick sina första elektriska spårvägar 22 augusti 1907. Spårvagnarna importerades från Tyskland. Stadens kollektivtrafik består idag av spårvagnar, trådbussar, bussar och minibussar (marshrutkas). Odessa har också en kabinbana.
En av stadens unika transportsystem är dess linbana från 1971. Linbanan går mellan staden och Otrada-stranden. Banan har 65 små gondoler som är målade med sovjetiska barnmotiv. Vagnarna stannar aldrig, vilket innebär att passagerarna får hoppa på och av i farten. Banans längd är 425 meter och når som högst 37 meter över havet.[13]
Gator och bebyggelse ligger utspridda på terrasserade kullar kring en liten hamn.[13] Arkitekturen i Odessa är starkt påverkad av Frankrike, Italien, renässans- och jugendarkitektur.[14]
Operahuset i Odessa är en av stadens mest populära sevärdheter.[4]
Potemkintrappan är också en populär sevärdhet bland turister samt en promenad längs Prymorskyj boulevard som ligger vid toppen av trappan.
Odessas katakomber är ett omfattande system av underjordiska tunnlar i och runt staden som anses vara världens längsta tunnelsystem, uppskattningsvis 2 500 kilometer långt.