Stress-related exhaustion symptoms have a high prevalence which is only likely to increase further in the near future. Understanding the physiological underpinnings of exhaustion has important implications for accurate diagnosis and the development of effective prevention and intervention programs. Given its integrative role in stress-regulation, the parasympathetic branch of the autonomic nervous systems has been a valid starting point in the exploration of the physiological mechanisms behind exhaustion. The aim of the present study was to examine the directionality and specificity of the association between exhaustion symptoms and vagally-mediated heart rate variability (vmHRV), a relatively pure measure of parasympathetic tone. Exhaustion symptoms and vmHRV were measured at four annually assessment waves (2015–2018) of the Dresden Burnout Study. A total sample of N = 378 participants who attended at least two of the four annual biomarker measurements were included in the present analyses. Cross-lagged multi-level panel modelling adjusting for various covariates (e.g., age, sex, BMI) revealed that vmHRV was meaningfully predictive of exhaustion symptoms and not vice versa. In addition, these effects were specific for exhaustion symptoms as no effect was shown for the other burnout sub-dimensions, or for depressive symptoms. Our findings indicate a clear link between exhaustion symptoms and vmHRV which may hold great potential for both enhancing the diagnosis and treatment of exhaustion symptoms.