Background and purpose: The aim of this study was to establish the cognitive profile of newly diagnosed untreated (de novo) patients with Parkinson's disease (PD) and more advanced, treated patients, and to determine the effects of dopamine (DA) replacement therapy. Methods: A cohort of 23 de novo patients, 55 mild to moderately advanced, medicated PD patients and 21 healthy controls participated. Cognitive tests included the Cambridge Examination for Mental Disorders and a battery of neuropsychological tests taken from the Cambridge Neuropsychological Test Automated Battery and the Vienna Test System. Results: De novo patients with PD were more impaired in working memory strategy use than healthy controls and treated patients with PD. Furthermore, the generation of random motor behaviour was more impaired in both de novo and treated PD patients than in healthy controls. Correlation analysis revealed that in treated patients with PD, ascending doses of dopaminergic medication were associated with poorer performance on a pattern recognition task. Conclusion: Selective impairments in strategy use and the generation of random motor behaviour are a very early feature of PD and might be of predictive value in further frontal cognitive deterioration. Furthermore, DA replacement therapy seems to improve frontal lobe function (strategy use) and worsen temporal lobe function (visual memory). © 2011 The Author(s). European Journal of Neurology © 2011 EFNS.