One barrier to interpreting past studies of cognition and major depressive disorder (MDD) has been the failure in many studies to adequately dissociate the effects of MDD from the potential cognitive side effects of selective serotonin reuptake inhibitors (SSRIs) use. To better understand how remediation of depressive symptoms affects cognitive function in MDD, we evaluated three groups of subjects: medication-naïve patients with MDD, medicated patients with MDD receiving the SSRI paroxetine, and healthy control (HC) subjects. All were administered a category-learning task that allows for dissociation between learning from positive feedback (reward) vs. learning from negative feedback (punishment). Healthy subjects learned significantly better from positive feedback than medication-naïve and medicated MDD groups, whose learning accuracy did not differ significantly. In contrast, medicated patients with MDD learned significantly less from negative feedback than medication-naïve patients with MDD and healthy subjects, whose learning accuracy was comparable. A comparison of subject’s relative sensitivity to positive vs. negative feedback showed that both the medicated MDD and HC groups conform to Kahneman and Tversky’s (1979) Prospect Theory, which expects losses (negative feedback) to loom psychologically slightly larger than gains (positive feedback). However, medicated MDD and HC profiles are not similar, which indicates that the state of medicated MDD is not “normal” when compared to HC, but rather balanced with less learning from both positive and negative feedback. On the other hand, medication-naïve patients with MDD violate Prospect Theory by having significantly exaggerated learning from negative feedback. This suggests that SSRI antidepressants impair learning from negative feedback, while having negligible effect on learning from positive feedback. Overall, these findings shed light on the importance of dissociating the cognitive consequences of MDD from those of SSRI treatment, and from cognitive evaluation of MDD subjects in a medication-naïve state before the administration of antidepressants. Future research is needed to correlate the mood-elevating effects and the cognitive balance between reward- and punishment-based learning related to SSRIs.