De første underjordiske stenminer begyndte at dukke op i det 19. århundrede, samtidig med at der blev bygget kraftigt i Odessa. De blev brugt som en kilde til billige byggematerialer. Kalksten blev skåret ved hjælp af save, og minedriften blev så intensiv, at det omfattende netværk af katakomber i anden halvdel af det 19. århundrede skabte mange ulemper for byen.

Indgang til katakomberne i Moldavanka på Kartamyshevskaya-gaden. Indgangene til katakomberne skal altid lukkes eller kontrolleres for at forhindre børn i at komme ind.

Efter den russiske revolution i 1917 blev stenbrydning forbudt i den centrale del af Odessa (inden for Porto-Franko-zonen, afgrænset af gaderne Gamle Port Franko og Panteleymonovskaya).

Under Anden Verdenskrig tjente katakomberne som skjulested for sovjetiske partisaner, især Vladimir Molodtsovs gruppe. I sit værk The Waves of The Black Sea beskrev Valentin Kataev kampen mellem sovjetiske partisaner mod aksestyrkerne under Odessa og den nærliggende forstad Usatove.

I 1961 blev klubben “Search” (Poisk) oprettet med henblik på at udforske partisanbevægelsens historie blandt katakomberne. Siden dens oprettelse har den udvidet forståelsen af katakomberne og givet oplysninger til at udvide kortlægningen af tunnellerne.

Byen har en stor befolkning på over 1 million mennesker, som nogle mener ville have gavn af indførelsen af et metrosystem. Tunnellerne er blevet nævnt som årsagen til, at et sådant metrosystem aldrig er blevet bygget i Odessa.

Siden begyndelsen af det 21. århundrede er kalkstensudvinding fortsat i minerne i Dofinovka, Byldynka og “Fomina balka” nær Odessa. Som følge af den moderne minedrift fortsætter katakomberne med at udvide sig.