Making Every Contact Count (MECC) is a national, long-term public health strategy in England. It supports public-facing workers to use opportunities during routine contacts to enable healthy lifestyle changes. This paper reports the findings from an external evaluation of voluntary and community sector (VCS) delivery of MECC in the North East of England, which focused on engaging under-represented client groups. The study aimed to (a) Establish if (and how) MECC had impacted the workforce, including changes to staff knowledge, confidence and behaviour; (b) Identify benefits, challenges and unintended consequences; and (c) Explore outcomes for service users. A multi-stage qualitative design focused on understanding both process and outcomes. The study utilised three data collection methods, including a journey mapping workshop (n = 20), semi-structured interviews with delivery leads, VCS workers and volunteers who had accessed MECC training (n = 11), and focus group discussions with clients (n = 22). The findings illustrated positive early outcomes, including improvements in self-reported staff knowledge and confidence as well as emerging examples of organisational culture shift and individual behaviour change. Alongside this, the data provided a rich picture of barriers and challenges which are examined at different levels—national programme, local programme, VCS sector, partner organisation, worker and client. The research highlights clear successes of the VCS delivery model. However, it is presented as a ‘double-edged sword,’ in light of associated challenges such as sector-level funding uncertainty and accessibility of MECC resources to diverse client groups. The discussion considers issues related to the measurement and attribution of behaviour change outcomes for brief interventions, as well as fidelity, legacy and long-term sustainability challenges. The recommendations call for system-level analysis and comparison of different MECC implementation models, to improve our understanding of challenges, opportunities and programme reach for behaviour change intervention programmes—particularly in relation to seldom-heard client groups.