Sediments sampled next to the Cíes Islands, a natural reserve of the National Park of Atlantic Islands in Ría de Vigo (Spain), 3 mo after the first tide of fuel from the ‘Prestige’tanker arrived, were chemically and microbiologically characterized. The chemical analysis of the sediments, using oil fingerprinting techniques, showed the occurrence of fresh ‘Prestige’fuel oil with a background of older hydrocarbon contamination. The cultured bacterial community of the contaminated sediments harbored a high population of total heterotrophs and alkane degraders and a small proportion of aromatic-degrading bacteria. Based on partial 16S ribosomal RNA gene sequence data, 37 different bacterial strains, isolated in diluted marine agar, were detected. Most of them were classified as members of the groups Gammaproteobacteria (59%) and Alphaproteobacteria (21%), although members of the Bacteroidetes (10%) and of Firmicutes (10%) were also found. Some of the different identified bacteria have previously been described as fuel oil–degrading species such as Alcanivorax, Shewanella, Vibrio, Pseudoalteromonas and Marinomonas. Seven independent isolates were able to grow with hexadecane. However, these 7 strains are grouped under the same phylotype, based on the 16S rRNA gene sequence, and were closely related to Alcanivorax borkumensis (Gammaproteobacteria). No aromatic-degrading activities were detected among the culturable bacteria. The presence of fresh fuel without a detected level of biodegradation suggests that Alcanivorax was an early colonizer after the ‘Prestige’oil spill. To our knowledge, the isolation of Alcanivorax from environmental samples without the aid of an enrichment procedure has not been previously reported. Our results suggest the ability of Alcanivorax to compete and coexist with other heterotrophic marine bacteria in an oil polluted marine environment rich in the nutrients N and P.