Marine hydrocarbon-degrading bacteria perform a fundamental role in the oxidation and ultimate removal of crude oil and its petrochemical derivatives in coastal and open ocean environments. Those with an almost exclusive ability to utilize hydrocarbons as a sole carbon and energy source have been found confined to just a few genera. Here we used stable isotope probing (SIP), a valuable tool to link the phylogeny and function of targeted microbial groups, to investigate hydrocarbon-degrading bacteria in coastal North Carolina sea water (Beaufort Inlet, USA) with uniformly labeled [13C]n-hexadecane. The dominant sequences in clone libraries constructed from 13C-enriched bacterial DNA (from n-hexadecane enrichments) were identified to belong to the genus Alcanivorax, with ≤98% sequence identity to the closest type strain – thus representing a putative novel phylogenetic taxon within this genus. Unexpectedly, we also identified 13C-enriched sequences in heavy DNA fractions that were affiliated to the genus Methylophaga. This is a contentious group since, though some of its members have been proposed to degrade hydrocarbons, substantive evidence has not previously confirmed this. We used quantitative PCR primers targeting the 16S rRNA gene of the SIP-identified Alcanivorax and Methylophaga to determine their abundance in incubations amended with unlabeled n-hexadecane. Both showed substantial increases in gene copy number during the experiments. Subsequently, we isolated a strain representing the SIP-identified Methylophaga sequences (99.9% 16S rRNA gene sequence identity) and used it to show, for the first time, direct evidence of hydrocarbon degradation by a cultured Methylophaga sp. This study demonstrates the value of coupling SIP with cultivation methods to identify and expand on the known diversity of hydrocarbon-degrading bacteria in the marine environment.