BACKGROUND: The Avahan programme has provided HIV prevention activities, including condom promotion, to female sex workers (FSWs) in southern India since 2004. Evidence suggests Avahan averted 202,000 HIV infections over 4 years. For replicating this intervention elsewhere, it is essential to understand how the intervention's impact could have been optimised for different budget levels. METHODS: Behavioural data were used to determine how condom use varied for FSWs with different levels of intervention intensity. Cost data from 64 Avahan districts quantified how district-level costs related to intervention scale and intensity. A deterministic model for HIV transmission amongst FSWs and clients projected the impact and cost of intervention strategies for different scale and intensity, and identified the optimal strategies that maximise impact for different budget levels. RESULTS: As budget levels increase, the optimal intervention strategy is to first increase intervention intensity which achieves little impact, then scale-up coverage to high levels for large increases in impact, and lastly increase intensity further for small additional gains. The cost-effectiveness of these optimal strategies generally improves with increasing resources, while straying from these strategies can triple costs for the same impact. Projections suggest Avahan was close to being optimal, and moderate budget reductions (≥ 20%) would have reduced impact considerably (>40%). DISCUSSION: Our analysis suggests that tailoring the design of HIV prevention programmes for FSWs can improve impact, and that a certain level of resources are required to achieve demonstrable impact. These insights are critical for optimising the use of limited resources for preventing HIV.