Major depression is associated with impairments of executive functions and affect perception deficits, both being linked to dysfunction of fronto-subcortical networks. So far, little is known about the relationship between cognitive and affective deficits in major depression. In the present investigation, affect perception and executive functions were assessed in 29 patients with a diagnosis of major depression (Dep) and 29 healthy controls (HC). Both groups were comparable on IQ, age, and gender distribution. Depressed patients showed deficits of perception of affective prosody, which were significantly related to inhibition, set shifting, and working memory. Our findings suggest a significant association between cognitive deficits and affect perception impairments in major depression, which may be of considerable clinical relevance and might be addressed in treatment approaches. Future studies are desirable to investigate the nature of the association in more detail.