Postexercise heart-rate (HR) recovery (HRR) indices have been associated with running and cycling endurance-exercise performance. The current study was designed (1) to test whether such a relationship also exists in the case of cross-country skiing (XCS) and (2) to determine whether the magnitude of any such relationship is related to the intensity of exercise before obtaining HRR indices. Ten elite male cross-country skiers (mean ± SD; 28.2 ± 5.4 y, 181 ± 8 cm, 77.9 ± 9.4 kg, 69.5 ± 4.3 mL · min-1 · kg-1 maximal oxygen uptake [VO2max]) performed 2 sessions of roller-skiing on a treadmill: a 2 × 3-km time trial and the same 6-km at an imposed submaximal speed followed by a final 800-m time trial. VO2 and HR were monitored continuously, while HRR and blood lactate (BLa) were assessed during 2 min immediately after each 6-km and the 800-m time trial. The 6-km time-trial time was largely negatively correlated with VO2max and BLa. On the contrary, there was no clear correlation between the 800-m time-trial time and VO2, HR, or BLa. In addition, in no case was any clear correlation between any of the HRR indices and performance time or VO2max observed. These findings confirm that XCS performance is largely correlated with VO2max and the ability to tolerate high levels of BLa; however, postexercise HRR showed no clear association with performance. The homogeneity of the group of athletes involved and the contribution of the arms and upper body to the exercise preceding determination of HRR may explain this absence of a relationship.