Staphylococcus aureus is an important human pathogen and a species whose evolution has been shaped in part by mobile genetic elements (MGEs). Our understanding of the evolutionary dynamics surrounding MGEs is incomplete, in particular how changes in the structure of multidrug-resistant (MDR) plasmids may influence clinically-relevant staphylococcal phenotypes. Here, we undertook a population- and functional-genomics study of 212 clinical methicillin-resistant S. aureus (MRSA) sequence types (ST) 239 isolates, recovered between 1980 and 2012 and representative of the two major lineages circulating in the region, to explore the evolution of the pSK1 family of MDR plasmids; illustrating how these plasmids have co-evolved with and contributed to the successful adaptation of this persistent healthcare-associated MRSA lineage. Using complete genomes and temporal phylogenomics we have reconstructed the evolution of the pSK1 plasmid family from its emergence in the late 1970s, with eight distinct structural variants having arisen within the ST239 MRSA population in Australia. Plasmid maintenance and stability was linked to IS256- and IS257-mediated structural changes, including chromosomal integration, inversion and disruption of plasmid replication machinery. Combining genomic findings with phenotypic susceptibility data for trimethoprim, gentamicin and the cationic biocide chlorhexidine, it appeared that the pSK1 family plasmids have contributed to enhanced resistance in ST239 MRSA through two mechanisms: (i) acquisition of plasmid-borne resistance mechanisms increasing rates of gentamicin resistance and reduced chlorhexidine susceptibility, and (ii) changes in plasmid configuration linked with further enhancement of chlorhexidine tolerance. While the exact mechanism of enhanced chlorhexidine tolerance in this population remains elusive, this research has uncovered a potential evolutionary response of ST239 MRSA to biocides, one which may contribute to the ongoing persistence and adaptation of this lineage within healthcare institutions.