BACKGROUND: The lack of availability of skilled providers in low- and middle- income countries is considered to be an important barrier to achieving reductions in maternal and child mortality. However, there is limited research on programs increasing the availability of skilled birth attendants in developing countries. We study the implementation of the Nigeria Midwives Service Scheme, a government program that recruited and deployed nearly 2,500 midwives to rural primary health care facilities across Nigeria in 2010. An outcome evaluation carried out by this team found only a modest impact on the use of antenatal care and no measurable impact on skilled birth attendance. This paper draws on perspectives of policymakers, program midwives, and community residents to understand why the program failed to have the desired impact. METHODS: We conducted semi-structured interviews with federal, state and local government policy makers and with MSS midwives. We also conducted focus groups with community stakeholders including community leaders and male and female residents. RESULTS: Our data reveal a range of design, implementation and operational challenges ranging from insufficient buy-in by key stakeholders at state and local levels, to irregular and in some cases total non-provision of agreed midwife benefits that likely contributed to the program's lack of impact. These challenges not only created a deep sense of dissatisfaction with the program but also had practical impacts on service delivery likely affecting households' uptake of services. CONCLUSION: This paper highlights the challenge of effectively scaling up maternal and child health interventions. Our findings emphasize the critical importance of program design, particularly when programs are implemented at scale; the need to identify and involve key stakeholders during planning and implementation; the importance of clearly defining lines of authority and responsibility that align with existing structures; and the necessity for multi-faceted interventions that address multiple barriers at the same time.