Access to safe and adequate food is a basic human right under Article 25 of the Universal Declaration of Human Rights. Globally, more than 870 million people consume less calories than they require, which can lead to disabling physical and mental health outcomes. This study was designed to investigate the association between household food insecurity and mental distress among mothers in the Tigray and SNNP regions of Ethiopia. A community based cross-sectional survey was completed on a total of 2,992 households. A linear multiple regression model was used to study the association between food insecurity and mental distress. More than half of the study participants, 57.9%, were experiencing food insecurity. The prevalence of mental distress among the mothers was 39%. Food insecurity was significantly associated with mental distress after controlling for socioeconomic covariates. Integrating screening and management of mental distress would result in a better health status of the mothers and those under their care.