Verbal fluency is commonly used as a proxy measure of executive functioning, as it involves cognitive flexibility, working memory, and inhibitory control. Previous research has demonstrated that crosswords can be a useful means of improving verbal fluency, results consistent with the cognitive reserve hypothesis; the form of verbal fluency affected has, however, differed across studies. The present study sought to assess the extent to which it was possible to target phonemic (PVF) and semantic verbal fluency (SVF) separately through word puzzles designed to focus on semantic/thematic and structural clues respectively. Fifty-three university students were randomly assigned to one of three groups: semantic/thematic, structural, or a daily diary control group. They were assessed on PVF and SVF at baseline, and immediately following a four-week intervention. Age, sex, and depression scores were controlled for. A 2 x 3 mixed ANCOVA showed that the structural group improved significantly more in PVF during the intervention period than did the semantic/thematic or control groups, with the improvement linked to improved switching performance. The effect size was large. No significant difference in improvement in SVF emerged, although the effect size was moderate. The findings support the notion that it is possible to improve specific forms of verbal fluency through tailored brief word-puzzle interventions.