Outcomes are reported from an evaluation performed between 2009 and 2010 of Project REPLACE, a programme developed as part of the national ‘Healthy Eating Health Action’ strategy by a Māori primary health organisation (PHO) in a regional centre of Aotearoa, New Zealand. Project REPLACE aimed to improve the health of the local Māori communities. Programme participants were invited to gradually change their behaviour by replacing behaviours potentially detrimental to health with healthier alternatives. The evaluation revealed that each community was innovative in their approaches to implementing Project REPLACE, drawing on their culture to combine healthy eating with increased exercise activities as well as measurements of achievement. The relationship that each coordinator had with the community was pivotal to the success of the programme. Project REPLACE highlighted the importance of Māori ownership and control of health initiatives.