Patients infected with the human immunodeficiency virus (HIV) are frequently exposed to antimicrobial agents. This might have an impact on the resistance profile, genetic background and virulence factors of colonizing Staphylococcus aureus. Sub-Saharan Africa is considered to be endemic for Panton-Valentine leukocidin (PVL) positive S. aureus which can be associated with skin and soft tissue infections (SSTI). We compared S. aureus from nasal and pharyngeal swabs from HIV patients (n = 141) and healthy controls (n = 206) in Gabon in 2013, and analyzed determinants of colonization with PVL positive isolates in a cross-sectional study. S. aureus isolates were screened for the presence of selected virulence factors (incl. PVL) and were subjected to antimicrobial susceptibility testing and genotyping. In HIV patients, S. aureus was more frequently detected (36.9 vs. 31.6%) and the isolates were more frequently PVL positive than in healthy controls (42.1 vs. 23.2%). The presence of PVL was associated with cotrimoxazole resistance (OR = 25.1, p < 0.001) and the use of cotrimoxazole was a risk factor for colonization with PVL positive isolates (OR = 2.5, p = 0.06). PVL positive isolates were associated with the multilocus sequence types ST15 (OR = 5.6, p < 0.001) and ST152 (OR = 62.1, p < 0.001). Participants colonized with PVL positive isolates reported more frequently SSTI in the past compared to carriers of PVL negative isolates (OR = 2.7, p = 0.01). In conclusion, the novelty of our study is that cotrimoxazole might increase the risk of SSTI in regions where cotrimoxazole resistance is high and associated with PVL. This finding needs to be confirmed in prospective studies.