Hospital-acquired infection is a major cause of morbidity and mortality, and regimes to prevent infection are crucial in infection control. These include the decolonization of vulnerable patients with methicillin-resistant Staphylococcus aureus (MRSA) carriage using antiseptics, including chlorhexidine and octenidine. Concern has been raised, however, regarding the possible development of biocide resistance. In this study, we assembled a panel of S. aureus isolates, including isolates collected before the development of chlorhexidine and octenidine and isolates, from a major hospital trust in the United Kingdom during a period when the decolonization regimes were altered. We observed significant increases in the MIC and minimum bactericidal concentration (MBC) of chlorhexidine in isolates from periods of high usage of chlorhexidine. Isolates with increased MICs and MBCs of octenidine rapidly emerged after octenidine was introduced in the trust. There was no apparent cross-resistance between the two biocidal agents. A combination of variable-number tandem repeat (VNTR) analysis, PCR for qac genes, and whole-genome sequencing was used to type isolates and examine possible mechanisms of resistance. There was no expansion of a single strain associated with decreased biocide tolerance, and biocide susceptibility did not correlate with carriage of qac efflux pump genes. Mutations within the NorA or NorB efflux pumps, previously associated with chlorhexidine export, were identified, however, suggesting that this may be an important mechanism of biocide tolerance. We present evidence that isolates are evolving in the face of biocide challenge in patients and that changes in decolonization regimes are reflected in changes in susceptibility of isolates.