Physical exercise is associated with parasympathetic withdrawal and increased sympathetic activity resulting in heart rate increase. The rate of post-exercise cardiodeceleration is used as an index of cardiac vagal reactivation. Analysis of heart rate variability (HRV) and complexity can provide useful information about autonomic control of the cardiovascular system. The aim of the present study was to ascertain the association between heart rate decrease after exercise and HRV parameters. Heart rate was monitored in 17 healthy male subjects (mean age: 20 years) during the pre-exercise phase (25 min supine, 5 min standing), during exercise (8 min of the step test with an ascending frequency corresponding to 70% of individual maximal power output) and during the recovery phase (30 min supine). HRV analysis in the time and frequency domains and evaluation of a newly developed complexity measure - sample entropy - were performed on selected segments of heart rate time series. During recovery, heart rate decreased gradually but did not attain pre-exercise values within 30 min after exercise. On the other hand, HRV gradually increased, but did not regain rest values during the study period. Heart rate complexity was slightly reduced after exercise and attained rest values after 30-min recovery. The rate of cardiodeceleration did not correlate with pre-exercise HRV parameters, but positively correlated with HRV measures and sample entropy obtained from the early phases of recovery. In conclusion, the cardiodeceleration rate is independent of HRV measures during the rest period but it is related to early post-exercise recovery HRV measures, confirming a parasympathetic contribution to this phase.