The ability to arrange thoughts and actions in an appropriate serial order (the problem of serial order) is essential to complex behaviors such as language, reasoning and cognitive planning. Patients with Parkinson's disease (PD) perform poorly in tasks that rely on the successful rearrangement of working memory representations. We hypothesized that serial ordering is impaired in nondemented patients with mild PD. We recruited 49 patients with mild idiopathic PD (Hoehn and Yahr Scale 1-2.5) and 51 matched healthy adults. Nineteen patients had normal global cognition (PD-NC, Montreal Cognitive Assessment, MoCA≥26/30) and thirty patients had mild cognitive impairment (PD-MCI, 21≤MoCA≤25). All participants underwent three working memory assessments: two experimental tests that require reordering random digits following a particular rule (adaptive digit ordering test and digit span backward test) and a control test that requires maintaining but no reordering (digit span forward test). PD-NC and PD-MCI patients performed significantly worse (with lower test scores and larger ordering costs) than healthy controls in both digit ordering and backward tests, although they performed normally in the forward test. The ordering cost increased as a function of age across groups, indicating an aging-related decline in the ability of serial ordering. However, individual patients' task performances were not correlated with their severity or duration of motor symptoms, or daily exposure to dopaminergic drugs. These results suggested that serial ordering deficits exist in early stages of PD, prior to subtle changes in global cognition and in parallel with motor symptoms.