Climate change poses daunting challenges to agricultural production and food security. Rising temperatures, shifting weather patterns, and more frequent extreme events have already demonstrated their effects on local, regional, and global agricultural systems. Crop varieties that withstand climate-related stresses and are suitable for cultivation in innovative cropping systems will be crucial to maximize risk avoidance, productivity, and profitability under climate-changed environments. We surveyed 588 expert stakeholders to predict current and novel traits that may be essential for future pearl millet, sorghum, maize, groundnut, cowpea, and common bean varieties, particularly in sub-Saharan Africa. We then review the current progress and prospects for breeding three prioritized future-essential traits for each of these crops. Experts predict that most current breeding priorities will remain important, but that rates of genetic gain must increase to keep pace with climate challenges and consumer demands. Importantly, the predicted future-essential traits include innovative breeding targets that must also be prioritized; for example, (1) optimized rhizosphere microbiome, with benefits for P, N, and water use efficiency, (2) optimized performance across or in specific cropping systems, (3) lower nighttime respiration, (4) improved stover quality, and (5) increased early vigor. We further discuss cutting-edge tools and approaches to discover, validate, and incorporate novel genetic diversity from exotic germplasm into breeding populations with unprecedented precision, accuracy, and speed. We conclude that the greatest challenge to developing crop varieties to win the race between climate change and food security might be our innovativeness in defining and boldness to breed for the traits of tomorrow.