Major depressive disorder (MDD) is a heterogeneous disorder. Our hypothesis is that neurological symptoms correlate with the severity of MDD symptoms. One hundred eighty-four outpatients with MDD completed a self-report questionnaire on past and present medical history. Patients were divided into three roughly equal depression severity levels based on scores from the APA Severity Measure for Depression—Adult (n = 66, 58, 60, for low, medium, high severity, respectively). We saw a significant and gradual increase in the frequency of “muscular paralysis” (1.5–5.2–16.7%) and “balance problems” (21.2–36.2–46.6%) from low to medium to high severity groups. We repeated the analysis using only the two most extreme severity categories: low severity (66 samples) vs. high severity (60 samples). High severity patients were also found to experience more “angina” symptoms than low severity patients (27.3 vs. 50%). The three significant clinical variables identified were introduced into a binary logistic regression model as the independent variables with high or low severity as the dependent variable. Both “muscular paralysis” and “balance problems” were significantly associated with increased severity of depression (odds ratio of 13.5 and 2.9, respectively), while “angina” was associated with an increase in severity with an odds ratio of 2.0, albeit not significantly. We show that neurological exam or clinical history could be useful biomarkers for depression severity. Our findings, if replicated, could lead to a simple clinical scale administered regularly for monitoring patients with MDD.