The Sahel is at the nexus of extreme ecological, socio-economic, and food security challenges where Green Revolution technologies have not been adopted and yields remain unchanged since the 1960s. Although the Parkland system where trees are maintained in cropped fields can have positive ecosystem outcomes, there is limited success for increasing yields at the landscape level. Here we report on a long-term study of inter-cropping with a local and overlooked evergreen shrub, Guiera senegalensis that offers a new approach to remediate degraded soils and increase crop productivity. A long-term factorial split-plot experiment of an optimized G. senegalensis intercropping system (~1500 shrubs ha−1 with coppiced residue additions to soils) compared to sole-cropping (as the main plot treatment) under four fertilizer treatments (0–1.5 times the recommended NPK rate) (as sub-plot treatment) was conducted relative to edaphic and agronomic performance of pearl millet (Pennisetum glaucum) and groundnut (Arachis hypogaea) in Senegal, West Africa. Contrary to conventional perspectives, G. senegalensis was non-competitive and indeed when coppiced there was a temporal offset of its fine root growth to the late rainy season when crop nutrient and water requirements are diminishing. The G. senegalensis intercropping system significantly increased crop yields, notably for millet where yields averaged across fertilizer treatments increased 126%. Importantly this system, over sole-cropping, maintained yields in low rainfall years which coincided with this system having significantly greater water use efficiency for both millet and groundnut. These responses were related to improved soil quality (increased particulate and total organic matter, and extractable nutrients). An important finding was that this system keeps surface soil temperatures below the critical 35 ℃, plant-physiological threshold during crop establishment which greatly improves crop emergence and early season growth. We conclude that this optimized shrub-intercropping system with its ability to produce abundant biomass (unpalatable to livestock) and unique ecological adaptation to coppicing, provides a logical approach for increasing food security and mitigating climate change. It is a local resource which subsistence farmers can directly utilize without external inputs or new infrastructure.