Staphylococcus aureus is a commensal that can also cause invasive infection. Reports suggest that nasal cocolonization occurs rarely, but the resources required to sequence multiple colonies have precluded its large-scale investigation. A staged protocol was developed to maximize detection of mixed-spa-type colonization while minimizing laboratory resources using 3,197 S. aureus-positive samples from a longitudinal study of healthy individuals in Oxfordshire, United Kingdom. Initial typing of pooled material from each sample identified a single unambiguous strain in 89.6% of samples. Twelve single-colony isolates were typed from samples producing ambiguous initial results. All samples could be resolved into one or more spa types using the protocol. Cocolonization point prevalence was 3.4 to 5.8% over 24 months of follow-up in 360 recruitment-positives. However, 18% were cocolonized at least once, most only transiently. Cocolonizing spa types were completely unrelated in 56% of samples. Of 272 recruitment-positives returning ≥12 swabs, 166 (61%) carried S. aureus continuously but only 106 (39%) carried the same single spa type without any cocolonization; 31 (11%) switched spa type and 29 (11%) had transient cocarriage. S. aureus colonization is dynamic even in long-term carriers. New unrelated cocolonizing strains could increase invasive disease risk, and ongoing within-host evolution could increase invasive potential, possibilities that future studies should explore.