Nigeria is one of few countries that reports having translated national policies on school-based comprehensive sexuality education (CSE) into near-nationwide implementation. We analysed data using the World Health Organization-ExpandNet framework, which provides a systematic structure for planning and managing the scaling up of health innovations. We examined how Nigeria's nationwide programme was designed and executed. Since 2002, Nigeria has developed a well thought through strategy to scale up CSE. Crucial attributes that facilitated the scaling up included technical consensus about the innovation and clarity about its components, dissection of a complex intervention into manageable components for implementation by organisations with complementary expertise, strong political leadership and championship in concert with advocacy and technical support from non-governmental organisations, proactive and energetic involvement of community stakeholders, effective programme management, and improvements to the information management system to ensure on-track implementation and mid-course corrections to keep stakeholders, including funders, informed and engaged. Challenges included programmatic values, competing priorities for available human resources and a lack of predictable funding for sustaining a rapid scale-up effort. Despite some weaknesses, implementation has largely proceeded according to plan. The lessons learned from Nigeria's experience can and should be used in other settings to achieve wide-scale coverage.