The objective of this dissertation research was to characterize sedimentary microbial populations that are active in degrading petroleum hydrocarbons that reach the seafloor during accidental oil spills. Whereas most previous work has investigated hydrocarbon-degrading microbial communities in sediments from seep environments that are regularly exposed to high levels of oil, the focus of this study was on non-seep sediments that are not pre-exposed to high levels of petroleum. Anaerobic degradation of petroleum hydrocarbons coupled to sulfate reduction was studied in muddy sediments collected from nearby the Mississippi River delta. Sediment-free enrichment cultures were established and the metabolically active microorganisms that degrade model alkanes and polycyclic aromatic hydrocarbons were characterized. In particular, sulfate-reducing bacteria that degrade the 3 ring PAH, phenanthrene, were identified for the first time in marine environments. The biochemical mechanisms of phenanthrene degradation under sulfate-reducing conditions were further investigated in enrichment cultures using a metagenomic approach. The succession of microbial populations that mediate aerobic hydrocarbon degradation was examined in an experiment conducted in situ at Pensacola Beach. Tarballs of Macondo oil collected from the Deepwater Horizon discharge were buried in beach sands and hydrocarbon-degrading microbial communities were characterized over a 3 year period. Overall, this study provides fundamental science to improve predictions of the fate of petroleum hydrocarbons that are deposited in marine sediments after an oil spill.