BACKGROUND: Violence against female sex workers (FSWs) can impede HIV prevention efforts and contravenes their human rights. We developed a multi-layered violence intervention targeting policy makers, secondary stakeholders (police, lawyers, media), and primary stakeholders (FSWs), as part of wider HIV prevention programming involving >60,000 FSWs in Karnataka state. This study examined if violence against FSWs is associated with reduced condom use and increased STI/HIV risk, and if addressing violence against FSWs within a large-scale HIV prevention program can reduce levels of violence against them. METHODS: FSWs were randomly selected to participate in polling booth surveys (PBS 2006-2008; short behavioural questionnaires administered anonymously) and integrated behavioural-biological assessments (IBBAs 2005-2009; administered face-to-face). RESULTS: 3,852 FSWs participated in the IBBAs and 7,638 FSWs participated in the PBS. Overall, 11.0% of FSWs in the IBBAs and 26.4% of FSWs in the PBS reported being beaten or raped in the past year. FSWs who reported violence in the past year were significantly less likely to report condom use with clients (zero unprotected sex acts in previous month, 55.4% vs. 75.5%, adjusted odds ratio (AOR) 0.4, 95% confidence interval (CI) 0.3 to 0.5, p < 0.001); to have accessed the HIV intervention program (ever contacted by peer educator, 84.9% vs. 89.6%, AOR 0.7, 95% CI 0.4 to 1.0, p = 0.04); or to have ever visited the project sexual health clinic (59.0% vs. 68.1%, AOR 0.7, 95% CI 0.6 to 1.0, p = 0.02); and were significantly more likely to be infected with gonorrhea (5.0% vs. 2.6%, AOR 1.9, 95% CI 1.1 to 3.3, p = 0.02). By the follow-up surveys, significant reductions were seen in the proportions of FSWs reporting violence compared with baseline (IBBA 13.0% vs. 9.0%, AOR 0.7, 95% CI 0.5 to 0.9 p = 0.01; PBS 27.3% vs. 18.9%, crude OR 0.5, 95% CI 0.4 to 0.5, p < 0.001). CONCLUSIONS: This program demonstrates that a structural approach to addressing violence can be effectively delivered at scale. Addressing violence against FSWs is important for the success of HIV prevention programs, and for protecting their basic human rights.