Cardiorespiratory fitness (CRF) is associated with mortality and cardiovascular disease, but assessing CRF in the population is challenging. Here we develop and validate a novel framework to estimate CRF (as maximal oxygen consumption, VO2max) from heart rate response to low-risk personalised exercise tests. We apply the method to examine associations between CRF and health outcomes in the UK Biobank study, one of the world's largest and most inclusive studies of CRF, showing that risk of all-cause mortality is 8% lower (95%CI 5-11%, 2670 deaths among 79,981 participants) and cardiovascular mortality is 9% lower (95%CI 4-14%, 854 deaths) per 1-metabolic equivalent difference in CRF. Associations obtained with the novel validated CRF estimation method are stronger than those obtained using previous methodology, suggesting previous methods may have underestimated the importance of fitness for human health.