Impaired ability to recall specific autobiographical memories is characteristic of depression, which when reversed, may have therapeutic benefits. This cluster-randomized controlled pilot trial investigated efficacy and aspects of acceptability, and feasibility of MEmory Specificity Training (MEST) relative to Psychoeducation and Supportive Counselling (PSC) for Major Depressive Disorder (N = 62). A key aim of this study was to determine a range of effect size estimates to inform a later phase trial. Assessments were completed at baseline, post-treatment and 3-month follow-up. The cognitive process outcome was memory specificity. The primary clinical outcome was symptoms on the Beck Depression Inventory-II at 3-month follow-up. The MEST group demonstrated greater improvement in memory specificity relative to PSC at post-intervention (d = 0.88) and follow-up (d = 0.74), relative to PSC. Both groups experienced a reduction in depressive symptoms at 3-month follow-up (d = 0.67). However, there was no support for a greater improvement in depressive symptoms at 3 months following MEST relative to PSC (d = -0.04). Although MEST generated changes on memory specificity and improved depressive symptoms, results provide no indication that MEST is superior to PSC in the resolution of self-reported depressive symptoms. Implications for later-phase definitive trials of MEST are discussed.