This study aimed to evaluate the efficacy of a diet and exercise lifestyle intervention on mental health outcomes for patients currently being treated for depression and/or anxiety in primary care. Patients (n=119) referred by general practitioners to the 12-week randomised controlled trial were assigned to either an intervention of six visits to a dual qualified dietitian/exercise physiologist (DEP) where motivational interviewing and activity scheduling were used to engage patients in individually-tailored lifestyle change (focussed on diet and physical activity), or an attention control with scheduled telephone contact. Assessments conducted at baseline (n=94) and 12 weeks (n=60) were analysed with an intent-to-treat approach using linear mixed modelling. Significant improvement was found for both groups on Depression, Anxiety and Stress Scale (DASS) scores, measures of nutrient intake and total Australian modified Healthy Eating Index (Aust-HEI) scores. Significant differences between groups over time were found only for iron intake and body mass index. Patients participating in individual consultations with a dietitian were more likely to maintain or improve diet quality than those participating in an attention control. This study provides initial evidence to support the role of dietitians in the management of patients with depression and/or anxiety.