Patients currently being treated for depression and/or anxiety were referred by their GP and randomised to a 12-week individually tailored diet and exercise lifestyle intervention or an attention control group. Assessments at baseline and 12 weeks included the Active Australia Survey for self-reported physical activity, chair stands, arm curls and a 3-min step test to measure physical fitness. Intent-to-treat analyses using linear mixed modelling showed both groups significantly improved participation in physical activity and muscular endurance. There were no significant differences in improvement between groups. The only group by time interaction was found for body mass index and indicated greater improvement in the intervention group compared to the attention control group. Motivated patients with depression and/or anxiety may be able to increase their participation in physical activity without regular individual support from an exercise physiologist. Alternate modes of support should be considered.