To better understand how medication status and task demands affect cognition in major depressive disorder (MDD), we evaluated medication-naïve patients with MDD, medicated patients with MDD receiving the selective serotonin reuptake inhibitors (SSRI) paroxetine, and healthy controls. All three groups were administered a computer-based cognitive task with two phases, an initial phase in which a sequence is learned through reward-based feedback (which our prior studies suggest is striatal-dependent), followed by a generalization phase that involves a change in the context where learned rules are to be applied (which our prior studies suggest is hippocampal-region dependent). Medication-naïve MDD patients were slow to learn the initial sequence but were normal on subsequent generalization of that learning. In contrast, medicated patients learned the initial sequence normally, but were impaired at the generalization phase. We argue that these data suggest (i) an MDD-related impairment in striatal-dependent sequence learning which can be remediated by SSRIs and (ii) an SSRI-induced impairment in hippocampal-dependent generalization of past learning to novel contexts, not otherwise seen in the medication-naïve MDD group. Thus, SSRIs might have a beneficial effect on striatal function required for sequence learning, but a detrimental effect on the hippocampus and other medial temporal lobe structures is critical for generalization.