Despite numerous international and national efforts, only 12 countries in the World Health Organization's African Region met the Millennium Development Goal #4 (MDG#4) to reduce under-five mortality by two-thirds by 2015. Given the variability across sub-Saharan Africa, a four-country study was undertaken to examine barriers and facilitators of child survival prior to 2015. Liberia and Zambia were chosen to represent countries making substantial progress towards MDG#4, while Kenya and Zimbabwe represented countries making less progress. Our individual case studies suggested that strong health governance and leadership (HGL) was a significant driver of the greater success in Liberia and Zambia compared with Kenya and Zimbabwe. To elucidate specific components of national HGL that may have substantially influenced the pace of reductions in child mortality, we conducted a cross-country analysis of national policies and strategies pertaining to maternal, neonatal and child health (MNCH) and qualitative interviews with individuals working in MNCH in each of the four study countries. The three aspects of HGL identified in this study which most consistently contributed to the different progress towards MDG#4 among the four study countries were (1) establishing child survival as a top national priority backed by a comprehensive policy and strategy framework and sufficient human, financial and material resources; (2) bringing together donors, strategic partners, health and non-health stakeholders and beneficiaries to collaborate in strategic planning, decision-making, resource-allocation and coordination of services; and (3) maintaining accountability through a 'monitor-review-act' approach to improve MNCH. Although child mortality in sub-Saharan Africa remains high, this comparative study suggests key health leadership and governance factors that can facilitate reduction of child mortality and may prove useful in tackling current Sustainable Development Goals.