Background: From 2014–2019, Latin America and the Caribbean had the fastest growth of moderate-to-severe food insecurity than any other region, rising from 22.9% to 31.7%. While the prevalence of food insecurity is higher among women than men in every continent, Latin America has the largest food insecurity gender gap. Factors contributing to this gender inequity include underrepresentation of women in formal employment, heightened burden of dependent care on women, and unequal compensation of labor for women vs. men. The objective of this study was to investigate the association between the gender of the head of the household, employment status of household members, and food insecurity in households with children in a low-income district of Lima, Peru. Methods: This cross-sectional study was carried out in Villa El Salvador, the fifth largest district in Metropolitan Lima, Peru, where over 20% of the population lives in poverty. Data were collected on a stratified random sample (n = 329) using a household questionnaire, including a validated food security tool (HFIAS). We ran multivariate logistic regression models predicting household food insecurity, with independent variables including gender of household head, education of household head, employment of household head, household-level employment status, age, and weekly food expenses per person. Results: In fully adjusted models, woman-headed households had almost thrice the odds of being food insecure compared to man-headed households. Education also had a significant effect size: a household whose household head did not complete high school was 3.4 times more likely to be food insecure than if they had some post-secondary education. Woman-headed households had a significantly higher proportion of members not formally employed, compared to man-headed households, but employment status was not associated with food insecurity. Conclusions: Gender of the household head was a major contributing factor to household food insecurity in Villa el Salvador. Gender dynamics affecting opportunities for employment, education, and non-remunerated work should inform national food security policies and interventions with the goal to not only lower food insecurity, but also reduce gender inequities in food insecurity and other nutritional outcomes.