Objective: The semantic fluency task is widely used in both clinical and research settings to assess both the integrity of the semantic store and the effectiveness of the search through it. Our aim was to investigate whether nondemented Parkinson’s disease (PD) patients show an impairment in the strategic exploration of the semantic store and whether the tested semantic category has an impact on multiple measures of performance. Method: We compared 74 nondemented PD patients with 254 healthy subjects in a semantic fluency test using relatively small (fruits) and large (animals) semantic categories. Number of words produced, number of explored semantic subcategories, and degree of order in the produced sequences were computed as dependent variables. Results: PD patients produced fewer words than healthy subjects did, regardless of the category. Number of subcategories was also lower in PD patients than in healthy subjects, without a significant difference between categories. Critically, PD patients’ sequences were less semantically organized than were those of controls, but this effect appeared in only the smaller category (fruits), thus pointing to a lack of strategy in exploring the semantic store. Conclusions: Our results show that the semantic fluency deficit in PD patients has a strategic component, even though that may not be the only cause of the impaired performance. Furthermore, our evidence suggests that the semantic category used in the test influences performance, hence providing an explanation for the failure by previous studies, which often used large categories such as animals, to detect strategy deficits in PD.