According to current estimates, the annual volume of crude oil entering the ocean due to both anthropogenic activities and naturally occurring seepages reaches approximately 8.3 million metric tons. Huge discharges from accidents have caused large-scale environmental disasters with extensive damage to the marine ecosystem. The natural clean-up of petroleum spills in marine environments is carried out primarily by naturally occurring obligate hydrocarbonoclastic bacteria (OHCB). The natural hosts of OHCB include a range of marine primary producers, unicellular photosynthetic eukaryotes and cyanobacteria, which have been documented as both, suppliers of hydrocarbon-like compounds that fuel the ‘cryptic’ hydrocarbon cycle and as a source of isolation of new OHCB. A very new body of evidence suggests that OHCB are not only the active early stage colonizers of plastics and hence the important component of the ocean’s ‘plastisphere’ but also encode an array of enzymes experimentally proven to act on petrochemical and bio-based polymers.