Although diverse bacteria capable of degrading petroleum hydrocarbons have been isolated and characterized, the vast majority of hydrocarbon-degrading bacteria, including anaerobes, could remain undiscovered, as a large fraction of bacteria inhabiting marine environments are uncultivable. Using culture-independent rRNA approaches, changes in the structure of microbial communities have been analyzed in marine environments contaminated by a real oil spill and in micro- or mesocosms that mimic such environments. Alcanivorax and Cycloclasticus of the gamma-Proteobacteria were identified as two key organisms with major roles in the degradation of petroleum hydrocarbons. Alcanivorax is responsible for alkane biodegradation, whereas Cycloclasticus degrades various aromatic hydrocarbons. This information will be useful to develop in situ bioremediation strategies for the clean-up of marine oil spills.