Background: Several studies have addressed the epidemiology of community-associated Staphylococcus aureus (CA-SA) in Europe; nonetheless, a comprehensive perspective remains unclear. In this study, we aimed to describe the population structure of CA-SA and to shed light on the origin of methicillin-resistant S. aureus (MRSA) in this continent. Methods and Findings: A total of 568 colonization and infection isolates, comprising both MRSA and methicillin-susceptible S. aureus (MSSA), were recovered in 16 European countries, from community and community-onset infections. The genetic background of isolates was characterized by molecular typing techniques (spa typing, pulsed-field gel electrophoresis and multilocus sequence typing) and the presence of PVL and ACME was tested by PCR. MRSA were further characterized by SCCmec typing. We found that 59% of all isolates were associated with community-associated clones. Most MRSA were related with USA300 (ST8-IVa and variants) (40%), followed by the European clone (ST80-IVc and derivatives) (28%) and the Taiwan clone (ST59-IVa and related clonal types) (15%). A total of 83% of MRSA carried Panton-Valentine leukocidin (PVL) and 14% carried the arginine catabolic mobile element (ACME). Surprisingly, we found a high genetic diversity among MRSA clonal types (ST-SCCmec), Simpson's index of diversity = 0.852 (0.788-0.916). Specifically, about half of the isolates carried novel associations between genetic background and SCCmec. Analysis by BURP showed that some CA-MSSA and CA-MRSA isolates were highly related, suggesting a probable local acquisition/loss of SCCmec. Conclusions: Our results imply that CA-MRSA origin, epidemiology and population structure in Europe is very dissimilar from that of USA.