The evolution of Staphylococcus aureus has been described as predominantly clonal, based on evidence from seven housekeeping genes. We aimed to test if this was also true for more polymorphic genes. In a collection of 60 isolates including major European epidemic methicillin-resistant S. aureus (MRSA) and sporadic MRSA strains, we compared the partial gene sequences of seven housekeeping genes (arcC, aroE, glpF, gmk, pta, tpi, and yqiL), six core adhesion genes (present in all strains) (clfA, clfB, fnbA, map, sdrC, and spa), and four accessory adhesion genes (not present in all strains) (ebpS, fnbB, sdrD, and sdrE). Nucleotide diversity of adhesion genes was 2- to 10-fold higher than genes used for multilocus sequence typing. All genes showed evidence for purifying selection with a weakly reduced level among accessory adhesion genes. Among these highly variable genes, there was no evidence for a difference in molecular evolution between epidemic and sporadic strains. Gene trees constructed from concatenated sequences of housekeeping, core adhesion, and accessory adhesion genes were highly congruent, indicating clonality, despite some evidence for homologous exchange. Further evidence for clonality was found with an overall positive correlation of allelic and nucleotidic divergence for both seven housekeeping genes and six core adhesion genes. However, for small allelic differences that fit the demarcations of clonal complexes (CCs) there was no such correlation, suggesting that recombination occurred. Therefore, despite an overall clonal population structure, recombination between related isolates within CCs might have contributed to S. aureus evolution.