Staphylococcus aureus is an important human pathogen that is renowned both for its rapid transmission within hospitals and the community, and for the formation of antibiotic resistant biofilms on medical implants. Recently, it was shown that S. aureus is able to spread over wet surfaces. This motility phenomenon is promoted by the surfactant properties of secreted phenol-soluble modulins (PSMs), which are also known to inhibit biofilm formation. The aim of the present studies was to determine whether any cell surface-associated S. aureus proteins have an impact on colony spreading. To this end, we analyzed the spreading capabilities of strains lacking non-essential components of the protein export and sorting machinery. Interestingly, our analyses reveal that the absence of sortase A (SrtA) causes a hyper-spreading phenotype. SrtA is responsible for covalent anchoring of various proteins to the staphylococcal cell wall. Accordingly, we show that the hyper-spreading phenotype of srtA mutant cells is an indirect effect that relates to the sortase substrates FnbpA, FnbpB, ClfA and ClfB. These surface-exposed staphylococcal proteins are known to promote biofilm formation, and cell-cell interactions. The hyper-spreading phenotype of srtA mutant staphylococcal cells was subsequently validated in Staphylococcus epidermidis. We conclude that cell wall-associated factors that promote a sessile lifestyle of S. aureus and S. epidermidis antagonize the colony spreading motility of these bacteria.