Major depressive disorder (MDD) is the most common non-motor manifestation of Parkinson’s disease (PD) affecting 50% of patients. However, little is known about the cognitive correlates of MDD in PD. Using a computer-based cognitive task that dissociates learning from positive and negative feedback, we tested four groups of subjects: (1) patients with PD with comorbid MDD, (2) patients with PD without comorbid MDD, (3) matched patients with MDD alone (without PD), and (4) matched healthy control subjects. Furthermore, we used a mathematical model of decision-making to fit both choice and response time data, allowing us to detect and characterize differences between the groups that are not revealed by cognitive results. The groups did not differ in learning accuracy from negative feedback, but the MDD groups (PD patients with MDD and patients with MDD alone) exhibited a selective impairment in learning accuracy from positive feedback when compared to the non-MDD groups (PD patients without MDD and healthy subjects). However, response time in positive feedback trials in the PD groups (both with and without MDD) was significantly slower than the non-PD groups (MDD and healthy groups). While faster response time usually correlates with poor learning accuracy, it was paradoxical in PD groups, with PD patients with MDD having impaired learning accuracy and PD patients without MDD having intact learning accuracy. Mathematical modeling showed that both MDD groups (PD with MDD and MDD alone) were significantly slower than non-MDD groups in the rate of accumulation of information for stimuli trained by positive feedback, which can lead to lower response accuracy. Conversely, modeling revealed that both PD groups (PD with MDD and PD alone) required more evidence than other groups to make responses, thus leading to slower response times. These results suggest that PD patients with MDD exhibit cognitive profiles with mixed traits characteristic of both MDD and PD, furthering our understanding of both PD and MDD and their often-complex comorbidity. To the best of our knowledge, this is the first study to examine feedback-based learning in PD with MDD while controlling for the effects of PD and MDD.