BACKGROUND: The planning, resourcing, implementation and monitoring of new programmes by district health managers is integral for success and sustainability. Ethiopia introduced the Community-Based Newborn Care programme in 2014 to improve newborn survival: an innovative component allowed community health workers to provide antibiotics for young infants with possible serious bacterial infection when referral was not possible. Informed by the World Health Organization health system building block framework, we aimed to study the capacity and operational challenges of introducing this new health service from the perspective of programme implementers and managers at the district level 20 months after programme initiation. METHODS: This qualitative study was part of a programme evaluation. From November to December of 2015, we conducted 28 semi-structured interviews with staff at district health offices, health centres and implementing Non-Governmental Organisations in 15 districts of four regions of Ethiopia. Verbatim transcripts were analysed using a priori and emerging themes. RESULTS: In line with the government's commitment to treat sick newborns close to their homes, participants reported that community health workers had been successfully trained to provide injectable antibiotics. However, the Community-Based Newborn Care programme was scaled up without allowing the health system to adapt to programme needs. There were inadequate processes and standards to ensure consistent availability of (1) trained staff for technical supervision, (2) antibiotics and (3) monitoring data specific to the programme. Furthermore, Non-Governmental Organizations played a central implementing role, which had implications for the long-term district level ownership and thus for the sustainability of the programme. CONCLUSION: In settings where sustainable local implementation depends on district-level health teams, new programmes should assess health system preparedness to absorb the service, and plan accordingly. Our findings can inform policy makers and implementers about the pre-conditions for a health system to introduce similar services and maximize long-term success.