There is growing interest in the potential of neuroimaging to help develop non-invasive biomarkers in neurodegenerative diseases. In this study, connection-wise patterns of functional connectivity were used to distinguish Parkinson's disease patients according to cognitive status using machine learning. Two independent subject samples were assessed with resting-state fMRI. The first (training) sample comprised 38 healthy controls and 70 Parkinson's disease patients (27 with mild cognitive impairment). The second (validation) sample included 25 patients (8 with mild cognitive impairment). The Brainnetome atlas was used to reconstruct the functional connectomes. Using a support vector machine trained on features selected through randomized logistic regression with leave-one-out cross-validation, a mean accuracy of 82.6% (p < 0.002) was achieved in separating patients with mild cognitive impairment from those without it in the training sample. The model trained on the whole training sample achieved an accuracy of 80.0% when used to classify the validation sample (p = 0.006). Correlation analyses showed that the connectivity level in the edges most consistently selected as features was associated with memory and executive function performance in the patient group. Our results demonstrate that connection-wise patterns of functional connectivity may be useful for discriminating Parkinson's disease patients according to the presence of cognitive deficits.