Gentamicin-susceptible methicillin-resistant Staphylococcus aureus (GS-MRSA) clones have gradually replaced gentamicin-resistant MRSA (GR-MRSA) clones in many European countries. We studied molecular and epidemiological aspects of MRSA strain replacement in individual patients. All patients from whom at least 2 MRSA strains showing different gentamicin susceptibility patterns were isolated between 1996 and 2008 were retrospectively identified. Staphylococcal cassette chromosome mec (SCCmec) type and clonality between isolates were determined using molecular methods. Risk factors for individual GR-MRSA SCCmec I (prevalent clone) strain replacement with GS-MRSA non-SCCmec I types were studied in a nested case-crossover study (n = 55 patients). MRSA strain replacement was observed in 127 patients, 85 (67%) of whom were initially colonized with GR-MRSA replaced subsequently by GS-MRSA. Most GS-MRSA replacement strains (50; 59%) possessed SCCmec IV. All MRSA isolate pairs from the same patient that consisted of different gentamicin susceptibility and SCCmec types were also genotypically different. Exposure to domiciliary nursing assistance (odds ratio [OR], 8.1; 95% confidence interval [CI], 1.2 to 53.7) and high Charlson scores (OR, 7.1; 95% CI, 1.1 to 46.8) were associated with individual strain replacement. In individual patients, exogenous acquisition of a different MRSA strain was responsible for strain replacement in most cases. Domiciliary nursing assistance could be a target for specific control measures to prevent transmission of GS-MRSA in our setting.