Az első földalatti kőbányák a 19. században kezdtek megjelenni, miközben Odesszában erőteljes építkezés folyt. Ezeket olcsó építőanyagok forrásaként használták. A mészkövet fűrészekkel vágták, és a bányászat olyan intenzívvé vált, hogy a 19. század második felére a katakombák kiterjedt hálózata sok kellemetlenséget okozott a városnak.
Az 1917-es orosz forradalom után Odessza központi részén (a Porto-Franko övezeten belül, amelyet a Régi Port Franko és a Pantelejmonovszkaja utcák határolnak) betiltották a kőbányászatot.
A második világháború alatt a katakombák szovjet partizánok, különösen Vlagyimir Molodcov osztagának rejtekhelyéül szolgáltak. Valentin Katajev A Fekete-tenger hullámai című művében leírta a szovjet partizánok harcát a tengelyhatalmak ellen, Odessza és a közeli külváros, Usatove alatt.
1961-ben létrehozták a “Keresés” (Poisk) klubot a katakombák között zajló partizánmozgalom történetének feltárására. Megalakulása óta bővítette a katakombák megértését, és információkat szolgáltatott az alagutak feltérképezésének bővítéséhez.
A város lakossága nagy, több mint 1 millió fő, és egyesek szerint a metrórendszer bevezetése előnyös lenne. Az alagutakra hivatkoztak, mint arra, hogy miért nem épült meg soha egy ilyen metrórendszer Odesszában.
A 21. század eleje óta folytatódik a mészkőbányászat az Odessza melletti Dofinovkában, Byldynkában és “Fomina balka” bányákban. A korabeli bányászat eredményeképpen a katakombák folyamatosan bővülnek.