We propose a cross-sectional study based on 980 maximal effort tests to quantify the effect of the calculation method of heart rate recovery (HRR) on its association with cardiorespiratory fitness (CRF). For five different time t0 after exercise cessation, HRR has been calculated as: • the difference and the ratio between maximal measured heart rate and heart rate (HR) at t0; • HR at t0; • the decay time of an exponential decay encompassing the first t0 minutes of the HR recovery. The associations between HRR indices and CRF were estimated from generalized estimating equations stratified by gender and adjusted for age and body mass index. For HRR indices based on exponential regression, no significant association with CRF was found, whereas the other HRR indices are associated with CRF when t0 is at least one minute and is maximum for t0 = 2 minutes for females and t0 = 3 minutes for males.