Based on the health action process approach (HAPA) this study examined whether changes in social cognition constructs could predict change in physical activity and fruit and vegetable intake for adult participants in My health for life, an Australian health promotion behaviour change program. Variance-based structural equation modelling was used to analyse data obtained from Australian adult program participants (n = 167) at baseline (T1), week 14 (T2), week 26 (T2), and 6-month post-program (T4). Change scores were calculated for the social cognition constructs and behaviour. Changes in action self-efficacy and outcome expectancies positively predicted changes in intentions. Action self-efficacy changes also predicted changes in maintenance self-efficacy which, in turn, mediated the effect of action self-efficacy on recovery self-efficacy and planning. Planning was predicted by changes in intentions and maintenance self-efficacy. Findings support the use of the HAPA model in designing complex health behaviour change interventions to achieve sustained behaviour change.