Food insecurity (FI) is a global concern and is one of the main causes of malnutrition in low- and middle-income countries. In Mozambique, the burden of FI and how various factors contribute to FI is not well known. This study aimed to investigate the prevalence of FI and its associated factors in southern Mozambique. Data from 1842 household heads in Maputo City were analyzed in a cross-sectional design. Food insecurity was measured using a modified version of the US Department of Agriculture Household Food Security scale, and its association with socio-demographic factors was assessed through multiple regressions. Altogether, 79% of the households were food insecure; of these, 16.6% had mild FI, 28.1% moderate and 34.4% severe FI. The study revealed that low-income households, those with less educated heads, and those engaged in informal work were significantly more prone to FI. Likewise, dietary diversity and the number of meals were also significant predictors of FI. These findings suggest the need for decent work and job creation, which calls for joint efforts from government, the private sector, and international institutions. Furthermore, these key drivers should be considered in the development of public health policies and programs designed to alleviate household FI and malnutrition in Mozambique.