Background: Understanding how food insecurity among women gives rise to differential patterning in HIV risks is critical for policy and programming in resource-limited settings. This is particularly the case in Brazil, which has undergone successive changes in the gender and socio-geographic composition of its complex epidemic over the past three decades. We used data from a national survey of Brazilian women to estimate the relationship between food insecurity and HIV risk. Methods and Findings: We used data on 12,684 sexually active women from a national survey conducted in Brazil in 2006–2007. Self-reported outcomes were (a) consistent condom use, defined as using a condom at each occasion of sexual intercourse in the previous 12 mo; (b) recent condom use, less stringently defined as using a condom with the most recent sexual partner; and (c) itchy vaginal discharge in the previous 30 d, possibly indicating presence of a sexually transmitted infection. The primary explanatory variable of interest was food insecurity, measured using the culturally adapted and validated Escala Brasiliera de Segurança Alimentar. In multivariable logistic regression models, severe food insecurity with hunger was associated with a reduced odds of consistent condom use in the past 12 mo (adjusted odds ratio [AOR] = 0.67; 95% CI, 0.48–0.92) and condom use at last sexual intercourse (AOR = 0.75; 95% CI, 0.57–0.98). Self-reported itchy vaginal discharge was associated with all categories of food insecurity (with AORs ranging from 1.46 to 1.94). In absolute terms, the effect sizes were large in magnitude across all outcomes. Underweight and/or lack of control in sexual relations did not appear to mediate the observed associations. Conclusions: Severe food insecurity with hunger was associated with reduced odds of condom use and increased odds of itchy vaginal discharge, which is potentially indicative of sexually transmitted infection, among sexually active women in Brazil. Interventions targeting food insecurity may have beneficial implications for HIV prevention in resource-limited settings.