Data on the impact of arterial stiffness on autonomic function are limited. We sought to investigate whether heart rate recovery (HRR), a predictor of autonomic function, is impaired in patients with increased arterial stiffness. A total of 475 participants (mean age 55.8 ± 11.1 years, 34.3% women) who underwent a treadmill exercise test (TET) for the evaluation of chest pain were retrospectively analyzed. All patients underwent brachial-ankle pulse wave velocity (baPWV) measurement on the same day. HRR was defined as the difference in heart rate from maximal exercise to 1 min of recovery. Participants with the lowest HRR tertile were older and had more cardiovascular risk factors than those with the highest HRR tertile. Simple correlation analysis showed that baPWV was negatively correlated with HRR (r = - 0.327, P < 0.001). In multiple linear regression analysis, there was a significant association between baPWV and HRR, even after adjusting for potential confounders (β = - 0.181, P < 0.001). In participants who underwent TET, baPWV was negatively correlated with HRR. The results of our study indicate a potential relationship between arterial stiffness and the autonomic nervous system.