BACKGROUND: Structural factors are known to affect individual risk and vulnerability to HIV. In the context of an HIV prevention programme for over 60,000 female sex workers (FSWs) in south India, we developed structural interventions involving policy makers, secondary stakeholders (police, government officials, lawyers, media) and primary stakeholders (FSWs themselves). The purpose of the interventions was to address context-specific factors (social inequity, violence and harassment, and stigma and discrimination) contributing to HIV vulnerability. We advocated with government authorities for HIV/AIDS as an economic, social and developmental issue, and solicited political leadership to embed HIV/AIDS issues throughout governmental programmes. We mobilised FSWs and appraised them of their legal rights, and worked with FSWs and people with HIV/AIDS to implement sensitization and awareness training for more than 175 government officials, 13,500 police and 950 journalists. METHODS: Standardised, routine programme monitoring indicators on service provision, service uptake, and community activities were collected monthly from 18 districts in Karnataka between 2007 and 2009. Daily tracking of news articles concerning HIV/AIDS and FSWs was undertaken manually in selected districts between 2005 and 2008. RESULTS: The HIV prevention programme is now operating at scale, with over 60,000 FSWs regularly contacted by peer educators, and over 17,000 FSWs accessing project services for sexually transmitted infections monthly. FSW membership in community-based organisations has increased from 8,000 to 37,000, and over 46,000 FSWs have now been referred for government-sponsored social entitlements. FSWs were supported to redress > 90% of the 4,600 reported incidents of violence and harassment reported between 2007-2009, and monitoring of news stories has shown a 50% increase in the number of positive media reports on HIV/AIDS and FSWs. CONCLUSIONS: Stigma, discrimination, violence, harassment and social equity issues are critical concerns of FSWs. This report demonstrates that it is possible to address these broader structural factors as part of large-scale HIV prevention programming. Although assessing the impact of the various components of a structural intervention on reducing HIV vulnerability is difficult, addressing the broader structural factors contributing to FSW vulnerability is critical to enable these vulnerable women to become sufficiently empowered to adopt the safer sexual behaviours which are required to respond effectively to the HIV epidemic.