Background: Protracted methamphetamine (MA) use is associated with decreased control over drug craving and altered brain volume in the frontostriatal network. However, the nature of volumetric changes following a course of psychological intervention for MA use is not yet known. Methods: 66 males (41 MA patients, 25 healthy controls, HC) between the ages of 18–50 were recruited, the MA patients from new admissions to an in-patient drug rehabilitation centre and the HC via public advertisement, both in Cape Town, South Africa. 17 MA patients received 4 weeks of treatment as usual (TAU), and 24 MA patients completed TAU plus daily 30-minute cognitive training (CT) using an N-back working memory task. Magnetic resonance imaging (MRI) at baseline and 4-week follow-up was acquired and voxel-based morphometry (VBM) was used for analysis. Results: TAU was associated with larger bilateral striatum (caudate/putamen) volume, whereas CT was associated with more widespread increases of the bilateral basal ganglia (incorporating the amygdala and hippocampus) and reduced bilateral cerebellum volume coinciding with improvements in impulsivity scores. Conclusions: While psychological intervention is associated with larger volume in mesolimbic reward regions, the utilisation of additional working memory training as an adjunct to treatment may further normalize frontostriatal structure and function.