A laboratory experiment was conducted to identify key hydrocarbon degraders from a marine oil spill sample (Prestige fuel oil), to ascertain their role in the degradation of different hydrocarbons, and to assess their biodegradation potential for this complex heavy oil. After a 17-month enrichment in weathered fuel, the bacterial community, initially consisting mainly of Methylophaga species, underwent a major selective pressure in favor of obligate hydrocarbonoclastic microorganisms, such as Alcanivorax and Marinobacter spp. and other hydrocarbon-degrading taxa (Thalassospira and Alcaligenes), and showed strong biodegradation potential. This ranged from >99% for all low- and medium-molecular-weight alkanes (C(15)-C(27)) and polycyclic aromatic hydrocarbons (C(0)- to C(2)- naphthalene, anthracene, phenanthrene, dibenzothiophene, and carbazole), to 75-98% for higher molecular-weight alkanes (C(28)-C(40)) and to 55-80% for the C(3) derivatives of tricyclic and tetracyclic polycyclic aromatic hydrocarbons (PAHs) (e.g., C(3)-chrysenes), in 60 days. The numbers of total heterotrophs and of n-alkane-, aliphatic-, and PAH degraders, as well as the structures of these populations, were monitored throughout the biodegradation process. The salinity of the counting medium affects the counts of PAH degraders, while the carbon source (n-hexadecane vs. a mixture of aliphatic hydrocarbons) is a key factor when counting aliphatic degraders. These limitations notwithstanding, some bacterial genera associated with hydrocarbon degradation (mainly belonging to α- and γ-Proteobacteria, including the hydrocarbonoclastic Alcanivorax and Marinobacter) were identified. We conclude that Thalassospira and Roseobacter contribute to the degradation of aliphatic hydrocarbons, whereas Mesorhizobium and Muricauda participate in the degradation of PAHs.