The association of major depressive disorder (MDD) with cardiovascular diseases (CVDs) through endothelial dysfunction is bidirectional. Circulating endothelial progenitor cells (cEPCs), essential for endothelial repair and function, are associated with risks of various CVDs. Here, the relationship of cEPC counts with MDD and the related clinical presentations were investigated in 50 patients with MDD and 46 healthy controls. In patients with MDD, a battery of clinical domains was analysed: depressed mood with Hamilton Depression Rating Scale (HAMD) and Montgomery–Åsberg Depression Rating Scale (MADRS), anxiety with Hamilton Anxiety Rating Scale (HAMA), cognitive dysfunction and deficit with Digit Symbol Substitution Test (DSST) and Perceived Deficits Questionnaire-Depression (PDQ-D), somatic symptoms with Depressive and Somatic Symptom Scale (DSSS), quality of life with 12-Item Short Form Health Survey (SF-12) and functional disability with Sheehan Disability Scale (SDS). Immature and mature cEPC counts were measured through flow cytometry. Increased mature and immature cEPC counts were significantly associated with higher anxiety after controlling the confounding effect of systolic blood pressure, and potentially associated with more severe depressive symptoms, worse cognitive performance and increased cognitive deficit, higher social disability, and worse mental health outcomes. Thus, cEPCs might have pleiotropic effects on MDD-associated symptoms and psychosocial outcomes.