Parkinson’s disease, typically thought of as a movement disorder, is increasingly recognized as causing cognitive impairment and dementia. Eye movement abnormalities are also described, including impairment of rapid eye movements (saccades) and the fixations interspersed between them. Such movements are under the influence of cortical and subcortical networks commonly targeted by the neurodegeneration seen in Parkinson’s disease and, as such, may provide a marker for cognitive decline. This study examined the error rates and visual exploration strategies of subjects with Parkinson’s disease, with and without cognitive impairment, whilst performing a battery of visuo-cognitive tasks. Error rates were significantly higher in those Parkinson’s disease groups with either mild cognitive impairment (P = 0.001) or dementia (P < 0.001), than in cognitively normal subjects with Parkinson’s disease. When compared with cognitively normal subjects with Parkinson’s disease, exploration strategy, as measured by a number of eye tracking variables, was least efficient in the dementia group but was also affected in those subjects with Parkinson’s disease with mild cognitive impairment. When compared with control subjects and cognitively normal subjects with Parkinson’s disease, saccade amplitudes were significantly reduced in the groups with mild cognitive impairment or dementia. Fixation duration was longer in all Parkinson’s disease groups compared with healthy control subjects but was longest for cognitively impaired Parkinson’s disease groups. The strongest predictor of average fixation duration was disease severity. Analysing only data from the most complex task, with the highest error rates, both cognitive impairment and disease severity contributed to a predictive model for fixation duration [F(2,76) = 12.52, P ≤ 0.001], but medication dose did not (r = 0.18, n = 78, P = 0.098, not significant). This study highlights the potential use of exploration strategy measures as a marker of cognitive decline in Parkinson’s disease and reveals the efficiency by which fixations and saccades are deployed in the build-up to a cognitive response, rather than merely focusing on the outcome itself. The prolongation of fixation duration, present to a small but significant degree even in cognitively normal subjects with Parkinson’s disease, suggests a disease-specific impact on the networks directing visual exploration, although the study also highlights the multi-factorial nature of changes in exploration and the significant impact of cognitive decline on efficiency of visual search.