Staphylococcus aureus is a common organism in orthopedic infections, but little is known about the genetic diversity of strains during an infectious process. Using periprosthetic joint infection (PJI) as a model, a prospective study was designed to quantify genetic variation among S. aureus strains both among and within patients. Whole genome sequencing and multilocus sequence typing was performed to genotype these two populations at high resolution. In nasal cultures, 78% of strains were of clonal complexes CC5, CC8, and CC30. In PJI cultures, only 63% could be classified in these common clonal complexes. The PJI cultures had a larger proportion of atypical strains, and these atypical strains were associated with poor host status and compromised immune conditions. Mutations in genes involved in fibronectin binding (ebh, fnbA, clfA, and clfB) systematically distinguished later PJI isolates from the first PJI isolate from each patient. Repeated mutations in S. aureus genes associated with extracellular matrix binding were identified, suggesting adaptive, parallel evolution of S. aureus during the development of PJI.