Background: Cognitive decline in Parkinson's disease (PD) has become increasingly recognized in recent years, and there is a need to identify methods for cognitive rehabilitation in PD patients. Objective: The aim of this study was to explore the feasibility and effects of 2 different computer-based cognitive rehabilitation (CBCR) interventions on attention, executive functions, and quality of life (QoL) in PD patients. Methods: Thirty nondemented PD patients were randomly assigned to one of 3 groups: one passive control group and 2 intervention groups with 2 different CBCR programmes. The intervention period was 8 weeks with follow-up visits in clinic every second week. Before and after the intervention period, patients were tested with a neuropsychological battery of attention, executive functions, and QoL. Results: Twenty-four patients completed the study. Patients in one of the CBCR groups experienced a significant within-group increase on the primary measures of attention, executive functions, and QoL. However, this effect was not significant between groups. No significant differences were observed for the other CBCR group or the control group. Conclusions: CBCR is a feasible intervention for cognitive rehabilitation in nondemented PD patients. The effects of training were modest and should be further explored in larger clinical trials. Some CBCR programmes might be more effective than others for PD patients.