Sunku nustatyti, kada po miestu atsiradusios pirmosios katakombos, kadangi jos vėliau būdavo platinamos. Visgi manoma, kad pirmieji požeminiai tuneliai čia pradėti kasti bent XVII a. Į įspūdingo dydžio labirintą ši sistema išaugo XIX a., kai iš ten iškasamas kalkakmenis buvo naudojamas pastatų statyboms mieste.
Odesos katakombas greitai pamėgo įvairūs sukilėliai, nusikaltėliai, ekscentrikai. Per Antrąjį pasaulinį karą sovietai buvo išvyti iš miesto, bet požemiuose paliko dešimtis suburtų ukrainiečių grupuočių.
Katakombose jos slėpėsi apie 13 mėnesių, tiesiai po mieste šeimininkaujančių nacių panosėmis, ir laukė tinkamos progos pulti. Žmonės žaisdavo šachmatais ir šaškėmis, klausydavo Sovietų Sąjungos radijo, darėsi valgyti – mėgino gyventi normalų gyvenimą, tik po žeme. Visgi, nemažai jų gyvybių pareikalavo prasta mityba ir ligos.
Naciai užmūrydavo kai kuriuos katakombų išėjimus, tikėdamiesi įkalinti ten besislapstančius žmones, kartais į jas įmesdavo liepsnojančius kanistrus.
Pasibaigus karui katakombos tapo nusikalstamų grupuočių slėptuvėmis. Nusikaltėliai tunelius ir platino, ir rausė naujus.
Dabar Ukrainoje susiformavusi ištisa katakombų tyrinėtojų subkultūra, kurie leidžiasi į kelių dienų žygius po žeme, mėgina aprašyti ir į žemėlapį suvesti milžinišką tunelių sistemą. Jie, gerai pažinodami šiuos labirintus, dažnai padeda surasti ir išgelbėti paklydėlius, kurie smalsumo vedini patys lenda į požemius ir ten pameta kelią.
Tuneliuose kartais vis dar randami sovietų partizanų ginklai, retkarčiais net ir jų palaikai. Yra keli atvejai, kai mirusiųjų kūnai buvo kone tobulai mumifikuoti – juos išdžiovindavo šaltas ir sausas tunelių oras.
Kaip ir dera požeminei apleistai vietai, katakombos apipintos legendomis. Pasakojama, kad ten sovietų partizanai vykdydavo žiaurias egzekucijas sučiuptiems naciams ir Odesą užėmusiems rumunams. Kalbama apie satanistus ar ten vykdomas okultizmo apeigas. Bene labiausiai žinomas pasakojimas – apie ten mirusią pasiklydusią paauglę.
Pasakojama, kad 2005 m. grupelė Odesos paauglių nusprendė Naujuosius sutikti surengiant vakarėlį katakombose. Viena mergina atsiskyrė nuo grupės ir pasiklydo. Ji tris dienas leido viena šaltyje ir aklinoje tamsoje, klaidžiodama po labirintus, kol galiausiai mirė nuo dehidratacijos. Policija jos kūną rado tik po dvejų metų.
Ši istorija yra plačiai paplitusi, tačiau ją pagrindžiančių faktų nėra, ir dažnas Odesos gyventojas tai pavadins pramanais.
Į katakombas patekti nėra nelegalu, tačiau tik nedidelė jų dalis yra oficialiai atverta visuomenei. Tiems, kas nori jose apsilankyti, primygtinai rekomenduojama kreiptis į profesionalus, kurie organizuoja ten turus.
