Sex workers in east and southern Africa are exposed to multiple occupational health and safety risks. Detailed understanding of barriers to accessing care would optimise design of improved services for this population. In this study, trained sex workers conducted 55 in-depth interviews and 12 focus group discussions with 106 female, 26 male and 4 transgender sex workers across 6 urban sites in Kenya, Zimbabwe, Uganda and South Africa. Data were analysed thematically, following an interpretive framework. Participants cited numerous unmet health needs, including diagnosis and treatment for sexually transmitted infections and insufficient access to condoms and lubricant. Denial of treatment for injuries following physical assault or rape and general hostility from public-sector providers was common. Resources permitting, many sex workers attended private services, citing higher quality and respect for dignity and confidentiality. Sex workers in southern Africa accessed specialised sex worker clinics, reporting mostly positive experiences. Across sites, participants called for additional targeted services, but also sensitisation and training of public-sector providers. Criminalisation of sex workers and associated stigmatisation, particularly of transgender and male sex workers, hinder HIV-prevention efforts and render access to mainstream healthcare precarious. Alongside law reform, sex worker-led peer outreach work should be strengthened and calls by sex workers for additional targeted services heeded.