The CGIAR Research Program (CRP) on Roots, Tubers and Bananas (RTB) includes vegetatively propagated staple crops linked by common breeding, seed, and postharvest issues, and by the frequency with which women are involved in their production and use. RTB crops are the backbone of food security across the humid tropics in sub-Saharan Africa (SSA) and in more localized areas of Asia and Latin America. Around 300 million poor people in developing countries currently depend on RTB value chains for food security, nutrition and income. Climate change poses challenges which could undo progress in poverty reduction and markedly increase food insecurity. This article examines planning and research for climate resilience across RTB crops, with a particular focus on the contrasting potato and sweet potato cases in SSA. A six-step framework for climate-smart breeding is proposed: (1) downscaling climate change models and crop modeling; (2) identifying and understanding key climate change responsive traits; (3) breeding and varietal selection; (4) phenotyping and genomic research to accelerate gains; (5) developing management options for climate-smart varieties; and (6) deployment (seed systems). In summary, climate-smart breeding means we need to do what we already do but faster, better, and smarter.