Major depressive disorders (MDD) are associated with an increased risk for cardiovascular morbidity and mortality. Even if it is known that MDD are accompanied by an autonomic dysbalance with increased sympathetic and/or reduced parasympathetic activity, to date only limited information is available about the degree and complexity of cardiovascular regulation. The aim of this study was to investigate the influence of MDD on the autonomous nervous system and cardiovascular complexity by means of linear and nonlinear indices from heart rate and blood pressure variability (HRV, BPV). From 57 non-medicated patients and 57 matched healthy controls with respect to age and gender HRV and BPV in time and frequency domain, symbolic dynamics, compression entropy, multiscale entropy, detrended fluctuation analysis, Poincaré plot analysis and baroreflex sensitivity were analysed from 30 min short-term recordings. Complexity indices from nonlinear dynamics demonstrated considerable changes in autonomous regulation due to MDD. For the first time we could show that non-medicated depressed patients who were matched with respect to age and gender reveal a significantly changed short-term as well as long-term complexity of cardiovascular regulation. These results suggest substantial changes in autonomic control probably due to a change of interactions between different physiological control loops in MDD.