School-based comprehensive sexuality education (CSE) can help adolescents achieve their full potential and realize their sexual and reproductive health and rights. This is particularly pressing in low- and middle-income countries (LMICs), where high rates of unintended pregnancy and STIs among adolescents can limit countries’ ability to capitalize on the demographic dividend. While many LMICs have developed CSE curricula, their full implementation is often hindered by challenges around program planning and roll-out at the national and local level. A better understanding of these barriers, and similarities and differences across countries, can help devise strategies to improve implementation; yet few studies have examined these barriers. This paper analyzes the challenges to the implementation of national CSE curricula in four LMICs: Ghana, Kenya, Peru and Guatemala. It presents qualitative findings from in-depth interviews with central and local government officials, civil society representatives, and community level stakeholders ranging from religious leaders to youth representatives. Qualitative findings are complemented by quantitative results from surveys of principals, teachers who teach CSE topics, and students aged 15–17 in a representative sample of 60–80 secondary schools distributed across three regions in each country, for a total of around 3000 students per country. Challenges encountered were strikingly similar across countries. Program planning-related challenges included insufficient and piecemeal funding for CSE; lack of coordination of the various efforts by central and local government, NGOs and development partners; and inadequate systems for monitoring and evaluating teachers and students on CSE. Curriculum implementation-related challenges included inadequate weight given to CSE when integrated into other subjects, insufficient adaptation of the curriculum to local contexts, and limited stakeholder participation in curriculum development. While challenges were similar across countries, the strategies used to overcome them were different, and offer useful lessons to improve implementation for these and other low- and middle-income countries facing similar challenges.