OBJECTIVE:We sought to understand and develop the critical elements of a program designed to promote physical health for people living with or experiencing mental illness. DESIGN:The study used a most significant change approach. Participants provided personal accounts of change, and these were analysed in a workshop with a range of stakeholders involved in program design and delivery. Core themes were identified to inform the development of the program. SETTING:The program is delivered by a community managed organisation in the South Eastern Illawarra region of New South Wales and the study took place in this setting. PARTICIPANTS:Participants included people who had accessed the Active8 program, staff who delivered the program, referrers and the funder of the program. MAIN OUTCOME MEASURES:Participants were invited to share stories of how the Active8 program had impacted them or the people they were supporting. RESULTS:Five key themes were identified as being critical to program success and development: (a) the right start at the right time; (b) a program that fits me; (c) health literacy leads to agency, action and change; (d) a chance to explore and establish healthy connections; and (e) change requires time, focus and ongoing support. CONCLUSION:Approaches that steer away from simple advice giving and towards empowering and motivating people in line with their individual needs, aspirations and social context show potential for enhancing health-behaviour change.