The hospital anxiety depression scale (HADS) is a benchmark used to investigate possible and probable cases of psychosomatic illness. Its affiliation with autonomic recovery after exercise is unclear and, as a technique applied to evaluate cardiovascular risk. We assessed a possible link between HADS and autonomic recovery after exercise. We studied healthy subjects split into two groups: Low HADS (n = 20) and High HADS (n = 21). Subjects consented to moderate aerobic exercise on a treadmill at 60% to 65% of the maximum heart rate (HR) for 30 min. We studied HR variability (HRV) before and during 30 min after exercise. Subjects with higher HADS values presented delayed recovery of HR and root-mean square of differences between adjacent normal RR intervals (RMSSD) after submaximal exercise. RMSSD during recovery from exercise had a significant association with HADS. In summary, subjects with higher HADS presented slower vagal recovery following exercise.