Timely diagnosis and treatment of sexually transmitted infections (STIs) is often hampered by the lack of symptoms, inadequate diagnostics and/or poor availability, accessibility and quality of treatment in resource-limited settings. Female sex workers (FSW) are highly vulnerable for HIV and key transmitters of STIs. Among FSW ( n = 400) participating in a prospective HIV incidence study in Kigali, Rwanda, only 15% (17/116) of women with laboratory-diagnosed non-ulcerative STIs at baseline reported symptoms. Only 27% (20/74) of women self-reporting genital symptoms sought care at enrolment, and 39% (46/117) of women with self-reported genital symptoms during follow-up. During focus group discussions, FSW considered treatment-seeking and partner notification important. Shame and feeling disrespected by doctors or other health-care workers were identified as barriers to seeking health care. A comprehensive STI control programme targeting both symptomatic and asymptomatic FSW should be considered in this setting.