The burden of sexually transmitted infections (STIs) in areas of sub-Saharan Africa with poor access to health care services is not well documented. In remote areas of South Africa, we investigated the prevalence of STIs and approaches to providing STI services through a mobile clinic. Methods We recruited 251 adult women visiting a mobile clinic that normally provides general health education and screening services, but not STI care. Clinical and sexual history was obtained and vaginal specimens were tested for Chlamydia trachomatis, Neisseria gonorrhoeae, Trichomonas vaginalis, and Mycoplasma genitalium infection and for Candida albicans and bacterial vaginosis. Results Laboratory test was positive for 133 (53%) of 251 women for at least 1 STI: C. trachomatis was observed in 52 (21%) women, N. gonorrhoeae in 39 (16%) women, T. vaginalis in 81 (32%) women and M. genitalium in 21 (8%) women. Eighty-one (32%) women met the criteria for vaginal discharge syndrome, of which 58% (47/81) would have been treated accurately. Among asymptomatic women 84 (49%) of 170 were diagnosed with an STI but untreated under the syndromic approach. We could not identify factors associated with asymptomatic STI infection. Conclusions There is a high unmet need for STI care in rural South African settings with poor access to health care services. Provision of STI services in a mobile clinic using the syndromic management approach provides a useful approach, but would have to be enhanced by targeted diagnostics to successfully address the burden of infection.