Social disadvantage is associated with being overweight, a poor diet and physical inactivity. The NHS Health Trainer Service (HTS) is a national initiative designed to promote behaviour change among socially disadvantaged people in England and Wales. This study reports pre–post changes in Body Mass Index (BMI), associated behaviours and cognitions among service users who set dietary or physical activity goals during a 12-month period (2008–2009; N = 4418). Sixty-nine percent of clients were from the two most deprived population quintiles and 94.7% were overweight or obese. Mean BMI decreased from 34.03 to 32.26, with overweight/obesity prevalence decreasing by 3.7%. There were increases in fruit and vegetable consumption, reductions in fried snack consumption, increases in frequency of moderate or intensive activity and gains in self-efficacy and perceived health and wellbeing. Clients with higher BMI, poorer diet or less activity at baseline achieved greater change. Findings suggest that the NHS HTS has the potential to improve population health and reduce health inequalities through behaviour change.