UNLABELLED: Successful navigation within the autobiographical memory store is integral to daily cognition. Impairment in the flexibility of memory retrieval can thereby have a detrimental impact on mental health. This randomised controlled phase II exploratory trial (N = 60) evaluated the potential of a novel intervention drawn from basic science - an autobiographical Memory Flexibility (MemFlex) training programme - which sought to ameliorate memory difficulties and improve symptoms of Major Depressive Disorder. MemFlex was compared to Psychoeducation (an evidence-based low-intensity intervention) to determine the likely range of effects on a primary cognitive target of memory flexibility at post-intervention, and co-primary clinical targets of self-reported depressive symptoms and diagnostic status at three-month follow-up. These effect sizes could subsequently be used to estimate sample size for a fully-powered trial. Results demonstrated small-moderate, though as expected statistically non-significant, effect sizes in favour of MemFlex for memory flexibility (d = 0.34, p = .20), and loss of diagnosis (OR = 0.65, p = .48), along with the secondary outcome of depression-free days (d = 0.36, p = .18). A smaller effect size was observed for between-group difference in self-reported depressive symptoms (d = 0.24, p = .35). Effect sizes in favour of MemFlex in this early-stage trial suggest that fully-powered evaluation of MemFlex may be warranted as an avenue to improving low-intensity treatment of depression. TRIAL REGISTRATION: ClinicalTrials.gov, Identifier NCT02371291.