Cognitive deficits are common in Parkinson's disease. Previous cross-sectional research has demonstrated a link between cognitive impairments and fronto-striatal dopaminergic dysmodulation. However, longitudinal studies that link disease progression with altered task-evoked brain activity are lacking. Therefore, our objective was to longitudinally evaluate working-memory related brain activity changes in Parkinson's disease patients with and without mild cognitive impairment (MCI). Patients were recruited within a longitudinal cohort study of incident patients with idiopathic parkinsonism. We longitudinally (at baseline examination and at 12-months follow-up) compared 28 patients with Parkinson's disease without MCI with 11 patients with Parkinson's disease and MCI. Functional MRI blood oxygen level dependent signal was measured during a verbal two-back working-memory task. Patients with MCI under-recruited bilateral medial prefrontal cortex at both time-points (main effect of group: p < 0.001, uncorrected). Critically, a significant group-by-time interaction effect (p < 0.001, uncorrected) was found in the right fusiform gyrus, indicating that working-memory related activity decreased for patients with Parkinson's disease and MCI between baseline and follow-up, while patients without MCI were stable across time-points. The functional connectivity between right fusiform gyrus and bilateral caudate nucleus was stronger for patients without MCI relative to patients with MCI. Our findings support the view that deficits in working-memory updating are related to persistent fronto-striatal under-recruitments in patients with early phase Parkinson's disease and MCI. The longitudinal evolution of MCI in Parkinson's disease translates into additional task-evoked posterior cortical changes.