Informal settlements in rapidly-growing African cities are urban and peri-urban spaces with high rates of formal unemployment, poverty, poor health outcomes, limited service provision, and chronic food insecurity. Traditional concepts of food deserts developed to describe North American and European cities do not accurately capture the realities of food inaccessibility in Africa’s urban informal food deserts. This paper focuses on a case study of informal settlements in the Namibian capital, Windhoek, to shed further light on the relationship between informality and food deserts in African cities. The data for the paper was collected in a 2016 survey and uses a sub-sample of households living in shack housing in three informal settlements in the city. Using various standard measures, the paper reveals that the informal settlements are spaces of extremely high food insecurity. They are not, however, food deprived. The proximity of supermarkets and open markets, and a vibrant informal food sector, all make food available. The problem is one of accessibility. Households are unable to access food in sufficient quantity, quality, variety, and with sufficient regularity.