For a long time the territory of the SW Crimea and adjacent shelf was considered as an area with uncertain or negative prospectivity for hydrocarbon exploration. Recent findings of clastic material called “heraclites” southeast of Sevastopol that derived from carbonate mats and buildups and related to submarine outgassing in the Lower Miocene sediments can speak quite the reverse. Heraclites upon the area of their first findings in the Heraclea Plateau in the SW Crimea are coarse clastic sediments inside Sarmatian sequence derived from destroyed calcareous hardground, i.e. proximal conglomerate tempestites, products of storm destruction of layered carbonate crust enriched with bituminous matter. Morphological attributes, mineralogy, geochemistry, and gas content of heraclites (carbonate angular and resin-like pebbles with high bituminous content) evidence their paragenetic relations to methanederived authigenic carbonate mats and mud volcanism. Heraclites are characterized by higher porosity (5-10%), unusual black or brown-black color, specific composition, silification and skeletal remains of benthic fauna. The main peculiarity of heraclites is their higher gas content and impregnation with residual oil. In the vicinity of Sevastopol heraclites occur mainly within the linear zones related to fault planes (Georgievsky, Chersonesos and Sevastopolsky faults) and contact zones of the overthrusts to outcrop in the area of 50 sq. km with estimated volume of 1.8 million of cubic meters. Along the Crimean South Coast several seams inside the Mid-Sarmatian bentonite-montmorillonite claystones (up to 6 separate layers) with sharp stratigraphic top and bottom contacts containing black gravels and angular limestone pebbles are traced starting from Streletskaya Bay to Cape Chersones and further to the south till Cape Phiolent. It is interesting to note that on the opposite side of the Black Sea were also described 6 levels of carbonate tempestites from Sarmatian (Bessarabian) sediments at Cape Kaliakra in Bulgaria. The analyses made have shown that gases contained in heraclites are identical upon their composition to modern mud volcanoes and white smoker cones related submarine gas seeps and speak in favor of their common paragenesis. Carbon dioxide presence in all samples and isotope composition of the carbonates under investigation allow assumption that Neogene outgassing is related to thermogenic processes accompanied by upward fault-controlled flux of deep fluids including hydrocarbons. Presence of hydrogen sulphide indicates that euxinic conditions were characteristic of the Black Sea from Neogene times. Methane dominates in heraclites, however, those ones enriched with paraffinic bitumens (0.12-0.14%) contain ethane and propane. Some traces of nitrogen testify that some intraclasts were exposed in subaerial environment. The fluid sources that responsible for formation of heraclites in the area broad Heraclean anticline are most probably are deepseated organic source rocks or even paleo- or recent hydrocarbon pools. There is also a concept that a flat-like intrusive magmatic body detected in that area on the depth of 10-40 km characterizing by intensive magnetic anomaly is contributing to fluid generation and migration. Recently the sign of the same process was recognized on the top of the Yayla Range near the Ai-Petri peak where it was found numerous black fibrous microsparite occurrences upon tension gashes and shear fractures pervading the Upper Jurassic limestone platform. The bituminous content of that microsparite testifies that those features are traces of paleo-hydrocarbon system (Miocene?) that now sealed by calcite of the latest generation. Resent drilling offshore Sevastopol has shown that Jurassic carbonates are full of the same migration bitumens upon fractures, sometimes manifesting live oil. This substantiates new perspectives for oil and gas exploration offshore the SW Crimea.