Background: Maternal and newborn health (MNH) still remains one of the major public health challenges worldwide, particularly in low and middle-income countries (LMICs) like Nepal. Different schemes to deliver free MNH services were introduced by the Nepal government decades ago; however, still nearly half of the women in the Madhesh province of Nepal do not utilise the complete MNH services. The systematic efforts to understand this slow progress and develop contextual solutions jointly with service users and wider stakeholders are lacking. Therefore, this study aimed to co-design initiatives to improve the delivery and uptake of MNH services in the Madhesh province of Nepal. Methods: This solution-focused research utilised a qualitative approach in combination with the participatory co-design method. This study was conducted over three stages: assessment, co-design and validation. The assessment stage involved 43 semi-structured interviews with diverse participants (service users, service providers and other stakeholders). The co-design workshop involved 33 diverse participants, and the validation workshop involved 17 diverse participants. The study’s wide range of diverse participants provides richness in the data. The data analysis followed Braun & Clark’s reflexive thematic analysis approach, and findings are presented under broader themes and subthemes. Results: The findings from the qualitative interviews are organised into four different overarching themes: i) Inadequate information and poor communication on free MNH services; ii) Perceptions and experiences of free MNH services; iii) Dynamics of decision making and support systems for MNH, and iv) Influences of federalised health governance on free MNH services. Findings from the qualitative interviews are fed into the co-design workshop to come up with jointly identified issues and co-designed initiatives with an aim to improve the utilisation and delivery of free MNH services. The jointly identified issues are grouped into five thematic headings: I) Poor quality of free MNH services, ii) Inadequate awareness and information, iii) Socio-cultural issues and practices, iv) Governance and management issues, and v) Poor engagement and coordination among stakeholders. In response to these issues, six co-designed initiatives are: a) Community-based motherhood mentorship, b) Men’s engagement in MNH promotion, c) Culturally inclusive IEC materials for MNH promotion d) Initiation of telehealth for MNH services, e) Establishing users’ feedback mechanism for MNH services, and f) Revitalisation of social audit for MNH services at the local health system. Conclusions: Different factors at the user, community and systemic levels were identified as both enablers and barriers in the uptake and delivery of free MNH services at local-level government health facilities. The co-design work with users and other wider stakeholders has identified six innovative, context-specific, realistic and feasible solutions with strong potential to improve the delivery and utilisation of free MNH services in the Madhesh province of Nepal. These initiatives warrant further research to pilot and evaluate their implementation.