Food insecurity has recently emerged as an important risk factor for HIV acquisition among women worldwide. No previous studies have used linked data that would permit investigation of the extent to which food insecurity may have differential associations with HIV transmission risk behaviors or symptoms of sexually transmitted infections (STIs) among men and women in the same households. We used nationally representative data on linked couples from the Nepal 2011 Demographic and Health Survey. The primary explanatory variable of interest was food insecurity, measured with a modified version of the Household Food Insecurity Access Scale. In multivariable logistic regression models, women in food insecure households were less likely to report recent condom use and more likely to report symptoms consistent with STIs. These patterns were absent among men. Interventions targeting food insecurity may have beneficial implications for both HIV prevention and gender equity in Nepal.