In this multicentre randomised controlled trial (RCT), 43 patients with Parkinson’s disease (PD) were randomly allocated to either the experimental condition receiving cognitive rehabilitation including strategy training (ReSET; Strategic Executive Treatment, n = 24) or to the control condition receiving computerised repetitive practice training for attention (Cogniplus, n = 16). We expected that strategy training (ReSET) would be more effective than cognitive training (Cogniplus) in improving patients’ everyday life executive functioning. Neuropsychological assessment was administered at baseline, at 2 weeks and 3–5 months post-treatment. Primary outcome measure was the Role Resumption List (RRL). Secondary outcome measures were treatment goal attainment (TGA), Dysexecutive Questionnaire (DEX), Parkinson’s Disease Questionnaire (PDQ-39), Zarit Burden Interview (ZBI) and neuropsychological tests. No effects of treatment were found on the primary outcome measure and on neuropsychological tests, except for one test of attention. At 2 weeks and 3–5 months post-treatment, PD patients in both the ReSET and Cogniplus group reported a significant improvement in everyday life executive functioning, as measured with TGA and the DEX-self, with an advantage for ReSET only shortly after treatment. Given these results and that PD patients were able to adhere to these treatments despite their motor symptoms and fatigue (i.e., the drop-out rate was small), we conclude that both strategy training and cognitive training for impairments in EF might be beneficial and feasible for PD patients.