BACKGROUND: High rates of partner change in 'upstream' sex work networks have long been recognized to drive 'downstream' transmission of sexually transmitted infections (STIs). We used a stochastic microsimulation model (STDSIM) to explore such transmission dynamics in a generalized African HIV epidemic. METHODS: We refined the quantification of sex work in Kisumu, Kenya, from the 4-cities study. Interventions with sex workers were introduced in 2000 and epidemics projected to 2020. We estimated the contribution of sex work to transmission, and modelled standard condom and STI interventions for three groups of sex workers at feasible rates of use and coverage. RESULTS: Removing transmission from sex work altogether would have resulted in 66% lower HIV incidence (range 54-75%) and 56% lower prevalence (range 44-63%) after 20 years. More feasible interventions reduced HIV prevalence from one-fifth to one-half. High rates of condom use in sex work had the greatest effect, whereas STI treatment contributed to HIV declines at lower levels of condom use. Interventions reaching the 40% of sex workers with most clients reduced HIV transmission nearly as much as less targeted approaches attempting to reach all sex workers. Declines were independent of antiretroviral therapy rollout and robust to realistic changes in parameter values. CONCLUSION: 'Upstream' transmission in sex work remains important in advanced African HIV epidemics even in the context of antiretroviral therapy. As in concentrated Asian epidemics, feasible condom and STI interventions that reach the most active sex workers can markedly reduce the size of HIV epidemics. Interventions targeting 'transactional' sex with fewer clients have less impact.