As primeiras minas subterrâneas de pedra começaram a aparecer no século XIX, enquanto que em Odessa se construíram vigorosamente. Eram utilizadas como fonte de materiais de construção baratos. A pedra calcária foi cortada com serras, e a mineração tornou-se tão intensiva que na segunda metade do século XIX, a extensa rede de catacumbas criou muitos inconvenientes para a cidade.

Entrada de catacumbas em Moldavanka na rua Kartamyshevskaya. As entradas das catacumbas devem estar sempre fechadas ou controladas para evitar a entrada de crianças.

Após a Revolução Russa de 1917, a mineração de pedras foi proibida na parte central de Odessa (dentro da zona Porto-Franko, delimitada pelas ruas Porto Franko e Panteleymonovskaya).

Durante a Segunda Guerra Mundial as catacumbas serviram de esconderijo para os partidários soviéticos, em particular a esquadra de Vladimir Molodtsov. Em sua obra As Ondas do Mar Negro, Valentin Kataev descreveu a batalha entre os partidários soviéticos contra as forças do eixo, sob Odessa e seu subúrbio vizinho Usatove.

Em 1961 foi criado o clube “Search” (Poisk) para explorar a história do movimento partidário entre as catacumbas. Desde a sua criação, expandiu a compreensão das catacumbas, e forneceu informações para expandir o mapeamento dos túneis.

A cidade tem uma grande população de mais de 1 milhão de pessoas, que alguns acreditam que seria beneficiada com a introdução de um sistema de metrô. Os túneis têm sido citados como a razão pela qual tal sistema de metrô nunca foi construído em Odessa.

Desde o começo do século 21, a mineração de calcário tem continuado nas minas localizadas em Dofinovka, Byldynka, e “Fomina balka” perto de Odessa. Como resultado da mineração contemporânea, as catacumbas continuam a expandir-se.