It is uncertain whether Sustainable Development Goal 2 (SDG2), a healthy diet for all, can be achieved in East Africa given its strong population growth, low agricultural yields, and the high perishability of nutrient-dense foods. We examine the consequences of a locally produced healthy diet on land use in a case study of the Arua district in Uganda. This type of analysis can alert policy makers to looming nutrition gaps and support the selection of alternative solution strategies. Using a linear programming (LP) model and three population growth projections, we estimate the minimum agricultural area needed in 2040 to produce a healthy diet that follows EAT-Lancet dietary diversity guidelines and supplies the average requirements of calories, proteins, Iron, and vitamin A. We also compare in scenarios to what extent i) production intensification, ii) food loss reduction, iii) by-product consumption, and iv) vitamin supplementation could reduce the required agricultural area. Results show that the necessary area to produce a healthy diet in 2040 is 160% larger than Arua’s current crop area and would greatly exceed the district’s total area. We also show that none of the changes proposed in our scenarios allows a sufficient increase in food production, suggesting that a mix of even more drastic changes across sectors will be necessary. The results underline the challenge for rural areas in East Africa like Arua to provide a healthy diet to its fast growing population, requiring integrated food system changes and policy coordination to orchestrate the increased availability of diverse and nutritious foods.