The bacterial communities in two different shoreline matrices, rocks and sand, from the Costa da Morte, northwestern Spain, were investigated 12 months after being affected by the Prestige oil spill. Culture-based and culture-independent approaches were used to compare the bacterial diversity present in these environments with that at a nonoiled site. A long-term effect of fuel on the microbial communities in the oiled sand and rock was suggested by the higher proportion of alkane and polyaromatic hydrocarbon (PAH) degraders and the differences in denaturing gradient gel electrophoresis patterns compared with those of the reference site. Members of the classes Alphaproteobacteria and Actinobacteria were the prevailing groups of bacteria detected in both matrices, although the sand bacterial community exhibited higher species richness than the rock bacterial community did. Culture-dependent and -independent approaches suggested that the genus Rhodococcus could play a key role in the in situ degradation of the alkane fraction of the Prestige fuel together with other members of the suborder Corynebacterineae. Moreover, other members of this suborder, such as Mycobacterium spp., together with Sphingomonadaceae bacteria (mainly Lutibacterium anuloederans), were related as well to the degradation of the aromatic fraction of the Prestige fuel. The multiapproach methodology applied in the present study allowed us to assess the complexity of autochthonous microbial communities related to the degradation of heavy fuel from the Prestige and to isolate some of their components for a further physiological study. Since several Corynebacterineae members related to the degradation of alkanes and PAHs were frequently detected in this and other supralittoral environments affected by the Prestige oil spill along the northwestern Spanish coast, the addition of mycolic acids to bioremediation amendments is proposed to favor the presence of these degraders in long-term fuel pollution-affected areas with similar characteristics.