This paper examines the political economic and governance challenges faced by African governments in operationalizing Climate-Smart Agriculture (CSA) as part of their pursuit of the United Nations Sustainable Development Goals (SDGs). There is a need to enrich our understanding of the diverse contexts and ways in which governments will have to navigate and address the inevitable choices and conflicts, synergies and trade-offs that will characterize efforts to simultaneously implement these global goals. Here we seek to develop an account of why and how countries are managing the interrelationship between SDGs, particularly those associated with food security and climate action. We develop explanations for the diversity in approaches and provide an initial assessment of what the consequences are for policy and practice. The analysis is informed by the contrasting experiences of four Eastern African countries, Kenya, Tanzania, Ethiopia, and Rwanda, as they seek to build more “climate resilient” food and agricultural systems that are compatible with achieving the SDGs.