Abattoir workers have been identified as high-risk for livestock-associated Staphylococcus aureus carriage. This study investigated S. aureus carriage in abattoir workers in Western Kenya. Nasal swabs were collected once from participants between February-November 2012. S. aureus was isolated using bacterial culture and antibiotic susceptibility testing performed using the VITEK 2 instrument and disc diffusion methods. Isolates underwent whole genome sequencing and Multi Locus Sequence Types were derived from these data. S. aureus (n = 126) was isolated from 118/737 (16.0%) participants. Carriage was higher in HIV-positive (24/89, 27.0%) than HIV−negative participants (94/648, 14.5%; p = 0.003). There were 23 sequence types (STs) identified, and half of the isolates were ST152 (34.1%) or ST8 (15.1%). Many isolates carried the Panton-Valentine leucocidin toxin gene (42.9%). Only three isolates were methicillin resistant S. aureus (MRSA) (3/126, 2.4%) and the prevalence of MRSA carriage was 0.4% (3/737). All MRSA were ST88. Isolates from HIV-positive participants (37.0%) were more frequently resistant to sulfamethoxazole/trimethoprim compared to isolates from HIV-negative participants (6.1%; p < 0.001). Similarly, trimethoprim resistance genes were more frequently detected in isolates from HIV-positive (81.5%) compared to HIV-negative participants (60.6%; p = 0.044). S. aureus in abattoir workers were representative of major sequence types in Africa, with a high proportion being toxigenic isolates. HIV-positive individuals were more frequently colonized by antimicrobial resistant S. aureus which may be explained by prophylactic antimicrobial use.