While food insecurity is a persistent public health challenge, its long-term association with depression at a national level is unknown. We investigated the spatial heterogeneity of food insecurity and its association with depression in South Africa (SA), using nationally-representative panel data from the South African National Income Dynamics Study (years 2008-2015). Geographical clusters ("hotpots") of food insecurity were identified using Kulldorff spatial scan statistic in SaTScan. Regression models were fitted to assess association between residing in food insecure hotspot communities and depression. Surprisingly, we found food insecurity hotspots (p < 0.001) in high-suitability agricultural crop and livestock production areas with reliable rainfall and fertile soils. At baseline (N = 15,630), we found greater likelihood of depression in individuals residing in food insecure hotspot communities [adjusted relative risk (aRR) = 1.13, 95% CI:1.01-1.27] using a generalized linear regression model. When the panel analysis was limited to 8,801 participants who were depression free at baseline, residing in a food insecure hotspot community was significantly associated with higher subsequent incidence of depression (aRR = 1.11, 95% CI:1.01-1.22) using a generalized estimating equation regression model. The association persisted even after controlling for multiple socioeconomic factors and household food insecurity. We identified spatial heterogeneity of food insecurity at a national scale in SA, with a demonstrated greater risk of incident depression in hotspots. More importantly, our finding points to the "Food Security Paradox", food insecurity in areas with high food-producing potential. There is a need for place-based policy interventions that target communities vulnerable to food insecurity, to reduce the burden of depression.