Pisana za vrijeme Ruskog Carstva, službena historija Odese kaže kako je carica Katarina II izdala proglas o osnivanju grada 1794. godine a drugi septembar smatraju rođendanom grada, najvećeg morskog grada Ukrajine.
Nestalo je tako najmanje četiri stoljeća historije grada, uključujući razdoblje od tri stotine godina, kada je Odesa, odnosno, Hadžibej i Kočibej bila dio Zlatne Horde, Krimskog kanata i Osmanskog Carstva.
Prvi spomen o mjestu budućeg grada je bitka kod Plavih voda 1362. godine. Tokom ove bitke, veliki vojvoda Algirdas od Litve porazio je snage emira Zlatne Horde, Kutlubuga, Hadžibeja i Demira. Poljski historičar Maciej Stryjkovsky opisao je ovako završnu bitku: "Tatari se nisu mogli oduprijeti dugom frontalnom napadu litvanskih snaga, bili su uplašeni i kao rezultat toga krenuli su neorganizirano u povlačenje. U bici su ubijena tri vladara, Kutlubah, Kačibej i Sultan Dimeyter, kao i puno mirza i ulana."
Nakon bitke kod Plavih voda, teritorija između Dnjestra i Dnjepra potpala je pod vlast Velikog vojvodstva Litvanije. Dvadesetih godina XV stoljeća vojvoda Vitautas sagradio je kameni dvorac u Khadzhibeyu, današnja Odesa. Godine 1482. iskoristivši slabljenje moći litvanskih prinčeva, krimski kan Mengli Giray napravio je pohod na Kijev, tokom kojeg su osvojene crnomorske zemlje Velikog vojvodstva Litvanije, uključujući dvorac Kochubey.
Dugo vremena Krimski kanat i Osmansko Carstvo su više ulagali u izgradnju lučkog grada Očakova (Ozyu) koji se nalazi nedaleko od Hadžibeja. No, sredinom XVIII stoljeća, Uzvišena Porta sagradila je malu Hadžibejovu utvrdu, jer su bili svjesni neizbježnog vojnog sukoba s Rusijom. Uz njega su izgrađeni skladišni objekti, a korak po korak razvijala se i lučka infrastruktura.
Godine 1766. ruski obavještajac Ivan Islenjev posjetio je Hadžibej pod krinkom trgovca i izradio plan tvrđave «novosagrađenog turskog grada Gadžibeja tik na moru». Među ostalim zgradama na planu Isleneva bila je i džamija. Nalazila se na mjestu današnjeg Književnog muzeja. Vjerojatno se radilo o maloj zgradi, s obzirom na to da je muslimansko stanovništvo u gradu bilo malo.
Godine 1789. ruske trupe upale su na Hadžibejevu tvrđavu. Većina zgrada je odmah uništena. Svi preživjeli stanovnici su iseljeni iz grada. Srušena je i džamija, ali niko ne zna točno, kada i pod kojim okolnostima.
Muslimanska zajednica se ponovno pojavila u grad, koji je postao poznat kao Odessa. U Državnom arhivu Odeske oblasti prvi akti o registraciji muslimana datiraju iz 1849. godine. Izgradnja "tatarske džamije" (u nekim dokumentima se naziva turskom) datira iz 1870. godine. Autorom projekta džamije smatra se istaknuti azerbejdžanski arhitekt Karbalayi Safikhan Karabakhi.
Danas ne samo da nema džamije već nije poznato ni tačno mjesto gdje se džamija nalazila. U ilustrovanom vodiču "Odesa 1900" piše da tramvaj "zaobilazi groblje, prolazi pored turske džamije i turskog groblja" a vidi se i na karti Odese objavljenoj 1919. godine, tik uz općinsko groblje koje je uključivalo "muhamedanski" sektor. Sovjetske vlasti su ga uništile '30-ih godina.
Najviše muslimana Odese dolazilo je s Volge i po porijeklu su bili Tatari i Baškiri, a među njima su bili i krimski Tatari. Godine 1892. oko 1.000 stanovnika Odese bili su muslimani. Zahvaljujući porodici Kalmykov, otvoreno je 16 trgovina "halal" mesa u različitim četvrtima grada.
Odesa je bila i centar organizacije hadža u Meku. Krajem XIX i početkom XX. stoljeća u gradu bi se okupljale hadžije iz cijelog Ruskog Carstva. Organizacija hadža bila je povjerena "Društvu za prevoz muslimanskih hodočasnika". Godine 1908. otvoren je han za hadžije. Početkom 30-ih godina 20. stoljeća zatvorena je luka za bliskoistočne parobrodove te je zabranjen prevoz hodočasnika u Meku.
