Background: Major depressive disorder (MDD) is associated with increased heart rate and reductions in its variability (HRV) – markers of future morbidity and mortality – yet prior studies have reported contradictory effects. We hypothesised that increases in heart rate and reductions in HRV would be more robust in melancholia relative to controls, than in patients with non-melancholia. Methods: A total of 72 patients with a primary diagnosis of MDD (age M: 36.26, SE: 1.34; 42 females) and 94 controls (age M: 35.69, SE: 1.16; 52 females) were included in this study. Heart rate and measures of its variability (HRV) were calculated from two 2-minute electrocardiogram recordings during resting state. Propensity score matching controlled imbalance on potential confounds between patients with melancholia (n=40) and non-melancholia (n=32) including age, gender, disorder severity and comorbid anxiety disorders. Results: MDD patients with melancholia displayed significantly increased heart rate and lower resting-state HRV (including the square root of the mean squared differences between successive N–N intervals, the absolute power of high frequency and standard deviation of the Poincaré plot perpendicular to the line of identity measures of HRV) relative to controls, findings associated with a moderate effect size (Cohens d’s = 0.56-0.58). Patients with melancholia also displayed an increased heart rate relative to those with non-melancholia (Cohen’s d = 0.20). Conclusion: MDD patients with melancholia – but not non-melancholia – display robust increases in heart rate and decreases in HRV. These findings may underpin a variety of behavioural impairments in patients with melancholia including somatic symptoms, cognitive impairment, reduced responsiveness to the environment, and over the longer-term, morbidity and mortality.