West Africa (WA) is among the most food insecure regions. Rapid human population growth and stagnating crop yields greatly contribute to this fact. Poor soil fertility, especially low plant available phosphorus (P) is constraining food production in the region. P-fertilizer use in WA is among the lowest in the world due to inaccessibility and high prices, often unaffordable to resource-poor subsistence farmers. This article provides an overview of soil P-deficiency in WA and opportunities to overcome it by exploiting sorghum and pearl millet genetic diversity. The topic is examined from the perspectives of plant breeding, soil science, plant physiology, plant nutrition, and agronomy, thereby referring to recent results obtained in a joint interdisciplinary research project, and reported literature. Specific objectives are to summarize: (1) The global problem of P scarcity and how it will affect WA farmers; (2) Soil P dynamics in WA soils; (3) Plant responses to P deficiency; (4) Opportunities to breed for improved crop adaptation to P-limited conditions; (5) Challenges and trade-offs for improving sorghum and pearl millet adaptation to low-P conditions in WA; and (6) Systems approaches to address soil P-deficiency in WA. Sorghum and pearl millet in WA exhibit highly significant genetic variation for P-uptake efficiency, P-utilization efficiency, and grain yield under P-limited conditions indicating the possibility of breeding P-efficient varieties. Direct selection under P-limited conditions was more efficient than indirect selection under high-P conditions. Combining P-uptake and P-utilization efficiency is recommendable for WA to avoid further soil mining. Genomic regions responsible for P-uptake, P-utilization efficiency, and grain yield under low-P have been identified in WA sorghum and pearl millet, and marker-assisted selection could be possible once these genomic regions are validated. Developing P-efficient genotypes may not, however, be a sustainable solution in itself in the long-term without replenishing the P removed from the system in harvested produce. We therefore propose the use of integrated soil fertility management and systems-oriented management such as enhanced crop-tree-livestock integration in combination with P-use-efficiency-improved varieties. Recycling P from animal bones, human excreta and urine are also possible approaches toward a partially closed and efficient P cycle in WA.