Background. Despite a paucity of evidence, decolonization measures are prescribed for out patients with recurrent Staphylococcus aureus skin and soft-tissue infection (SSTI). Objective. Compare the effectiveness of 4 regimens for eradicating S. aureus carriage. Design. Open-label, randomized controlled trial. Colonization status and recurrent SSTI were ascertained at 1 and 4 months. Setting. Barnes-Jewish and St. Louis Children's Hospitals, St. Louis, Missouri, 2007-2009. Participants. Three hundred patients with community-onset SSTI and S. aureus colonization in the nares, axilla, or inguinal folds. Interventions. Participants were randomized to receive no therapeutic intervention (control subjects) or one of three 5-day regimens: 2% mupirocin ointment applied to the nares twice daily, intranasal mupirocin plus daily 4% chlorhexidine body washes, or intranasal mupirocin plus daily dilute bleach water baths. Results. Among 244 participants with 1-month colonization data, modified intention-to-treat analysis revealed S. aureus eradication in 38% of participants in the education only (control) group, 56% of those in the mupirocin group (P =.03 vs controls), 55% of those in the mupirocin and chlorhexidine group (P =.05), and 63% off those in the mupirocin and bleach group (P =.006). Of 229 participants with 4-month colonization data, eradication rates were 48% in the control group, 56% in the mupirocin only group (P =.40 vs controls), 54% in the mupirocin and chlorhexidine group (P =.51), and 71% in the mupirocin and bleach group (P =.02). At 1 and 4 months, recurrent SSTIs were reported by 20% and 36% of participants, respectively. Conclusions. An inexpensive regimen of dilute bleach baths, intranasal mupirocin, and hygiene education effectively eradicated S. aureus over a 4-month period. High rates of recurrent SSTI suggest that factors other than endogenous colonization are important determinants of infection.