Objectives: We investigated whether a Mediterranean-style diet (MedDiet) supplemented with fish oil can improve mental health in adults suffering depression. Methods: Adults with self-reported depression were randomized to receive fortnightly food hampers and MedDiet cooking workshops for 3 months and fish oil supplements for 6 months, or attend social groups fortnightly for 3 months. Assessments at baseline, 3 and 6 months included mental health, quality of life (QoL) and dietary questionnaires, and blood samples for erythrocyte fatty acid analysis. Results: n = 152 eligible adults aged 18–65 were recruited (n = 95 completed 3-month and n = 85 completed 6-month assessments). At 3 months, the MedDiet group had a higher MedDiet score (t = 3.95, P < 0.01), consumed more vegetables (t = 3.95, P < 0.01), fruit (t = 2.10, P = 0.04), nuts (t = 2.29, P = 0.02), legumes (t = 2.41, P = 0.02) wholegrains (t = 2.63, P = 0.01), and vegetable diversity (t = 3.27, P < 0.01); less unhealthy snacks (t = −2.10, P = 0.04) and red meat/chicken (t = −2.13, P = 0.04). The MedDiet group had greater reduction in depression (t = −2.24, P = 0.03) and improved mental health QoL scores (t = 2.10, P = 0.04) at 3 months. Improved diet and mental health were sustained at 6 months. Reduced depression was correlated with an increased MedDiet score (r = −0.298, P = 0.01), nuts (r = −0.264, P = 0.01), and vegetable diversity (r = −0.303, P = 0.01). Other mental health improvements had similar correlations, most notably for increased vegetable diversity and legumes. There were some correlations between increased omega-3, decreased omega-6 and improved mental health. Discussion: This is one of the first randomized controlled trials to show that healthy dietary changes are achievable and, supplemented with fish oil, can improve mental health in people with depression.