While Kenya has had a long-standing national HIV-prevention programme, evidence on the level of exposure to its interventions and related effects on behavioural changes among female sex workers (FSWs) is limited. Using cross-sectional behavioural data collected in 2013 from 1 357 FSWs aged 18 years and above in Nairobi, Kenya, this study explores the relationship between FSW programme exposure levels and behavioural outcomes including condom use, sexually transmitted infection (STI)-treatment, and empowerment measures like disclosure of self-identity and violence reporting. We categorised programme exposure levels as none, moderate and intensive. Multivariate logistic regression was used for analysis. Overall, 35% of the FSWs were not exposed to any HIV prevention programme, whereas about 24% had moderate and 41% had intensive exposure. FSWs having intensive programme exposure had a higher likelihood of using condoms consistently with occasional clients (AOR: 1.57; 95% CI: 1.08-2.31) and seeking treatment for STIs (AOR: 3.37; 95% CI: 1.63-7.02) compared to FSWs with no or moderate exposure. Intensive programme exposure was also associated with higher self-disclosure of sex-work identity (AOR: 1.63; 95% CI: 1.19-2.24), reporting of violence to police (AOR: 2.45; 95% CI: 1.03-5.84), and negotiation of condom use at last sex when the client was under the influence of alcohol (AOR: 1.63; 95% CI: 0.94-2.82). Although HIV prevention programmes in Kenya have been underway for over a decade, programme efforts were largely focused on saturating the coverage (intervention breadth). Strategies should now focus on ensuring improved quality of contacts through intensified programme exposure (intervention depth) to enhance gains in behavioural change among FSWs and preventing the burden of HIV infection among them.