Verbal fluency tests (VFT) are often used to assess executive functioning in Parkinson's disease (PD). Various cognitive functions may, however, impair performance on VFT. Furthermore, since PD is a progressive neurodegenerative disease, it is also not clear whether deficits on VFT reflect impairments in the same cognitive functions throughout the different disease stages. This study will investigate what is measured with VFT in PD, in particular at different disease stages. Eighty-eight PD patients and 65 healthy participants, matched for age, gender, and education, were included. All were assessed with semantic and phonemic VFT and tests assessing executive functions, memory, and psychomotor speed. Mild and moderate PD patients did not differ in the number of words generated on both VFT. However, mild and moderate PD patients differed significantly with regard to the size of the largest cluster and the number of intra-dimensional shifts on phonemic VFT. Furthermore, at the mild disease stages, psychomotor speed predicted the performance on both VFT; whereas at the moderate stages of the disease, cognitive flexibility and psychomotor speed predicted the performance on both VFT. In conclusion, different cognitive functions underlie the performances of PD patients at different stages of the disease on semantic and phonemic VFT. Impairments in VFT, therefore, do not necessarily represent a specific deficit of executive functioning in patients with PD but should rather be interpreted in the context of disease severity and dysfunctions in other domains of cognition.