Heart rate recovery (HRR) after submaximal exercise improves after training. However, it is unknown if this also occurs in already well-trained cyclists. Therefore, 14 well-trained cyclists (VO2max 60.3 ± 7.2 ml kg−1 min−1; relative peak power output 5.2 ± 0.6 W kg−1) participated in a high-intensity training programme (eight sessions in 4 weeks). Before and after high-intensity training, performance was assessed with a peak power output test including respiratory gas analysis (VO2max) and a 40-km time trial. HRR was measured after every high-intensity training session and 40-km time trial. After the training period peak power output, expressed as W kg−1, improved by 4.7% (P = 0.000010) and 40-km time trial improved by 2.2% (P = 0.000007), whereas there was no change in VO2max (P = 0.066571). Both HRR after the high intensity training sessions (7 ± 6 beats; P = 0.001302) and HRR after the 40-km time trials (6 ± 3 beats; P = 0.023101) improved significantly after the training period. Good relationships were found between improvements in HRR40-km and improvements in peak power output (r = 0.73; P < 0.0001) and 40-km time trial time (r = 0.96; P < 0.0001). In conclusion, HRR is a sensitive marker which tracks changes in training status in already well-trained cyclists and has the potential to have an important role in monitoring and prescribing training.