The epidemiologically most important mechanism of antibiotic resistance in Staphylococcus aureus is associated with mecA–an acquired gene encoding an extra penicillin-binding protein (PBP2a) with low affinity to virtually all β-lactams. The introduction of mecA into the S. aureus chromosome has led to the emergence of methicillin-resistant S. aureus (MRSA) pandemics, responsible for high rates of mortality worldwide. Nonetheless, little is known regarding the origin and evolution of mecA. Different mecA homologues have been identified in species belonging to the Staphylococcus sciuri group representing the most primitive staphylococci. In this study we aimed to identify evolutionary steps linking these mecA precursors to the β-lactam resistance gene mecA and the resistance phenotype. We sequenced genomes of 106 S. sciuri, S. vitulinus and S. fleurettii strains and determined their oxacillin susceptibility profiles. Single-nucleotide polymorphism (SNP) analysis of the core genome was performed to assess the genetic relatedness of the isolates. Phylogenetic analysis of the mecA gene homologues and promoters was achieved through nucleotide/amino acid sequence alignments and mutation rates were estimated using a Bayesian analysis. Furthermore, the predicted structure of mecA homologue-encoded PBPs of oxacillin-susceptible and -resistant strains were compared. We showed for the first time that oxacillin resistance in the S. sciuri group has emerged multiple times and by a variety of different mechanisms. Development of resistance occurred through several steps including structural diversification of the non-binding domain of native PBPs; changes in the promoters of mecA homologues; acquisition of SCCmec and adaptation of the bacterial genetic background. Moreover, our results suggest that it was exposure to β-lactams in human-created environments that has driven evolution of native PBPs towards a resistance determinant. The evolution of β-lactam resistance in staphylococci highlights the numerous resources available to bacteria to adapt to the selective pressure of antibiotics.