Little is known about the combined associations of cardiorespiratory fitness (CRF) and hand grip strength (GS) with mortality in general adult populations. The purpose of this study was to compare the relative risk of mortality for CRF, GS, and their combination. In UK Biobank, a prospective cohort of > 0.5 million adults aged 40-69 years, CRF was measured through submaximal bike tests; GS was measured using a hand-dynamometer. This analysis is based on data from 70,913 men and women (832 all-cause, 177 cardiovascular and 503 cancer deaths over 5.7-year follow-up) who provided valid CRF and GS data, and with no history of heart attack/stroke/cancer at baseline. Compared with the lowest CRF category, the hazard ratio (HR) for all-cause mortality was 0.76 [95% confidence interval (CI) 0.64-0.89] and 0.65 (95% CI 0.55-0.78) for the middle and highest CRF categories, respectively, after adjustment for confounders and GS. The highest GS category had an HR of 0.79 (95% CI 0.66-0.95) for all-cause mortality compared with the lowest, after adjustment for confounders and CRF. Similar results were found for cardiovascular and cancer mortality. The HRs for the combination of highest CRF and GS were 0.53 (95% CI 0.39-0.72) for all-cause mortality and 0.31 (95% CI 0.14-0.67) for cardiovascular mortality, compared with the reference category of lowest CRF and GS: no significant association for cancer mortality (HR 0.70; 95% CI 0.48-1.02). CRF and GS are both independent predictors of mortality. Improving both CRF and muscle strength, as opposed to either of the two alone, may be the most effective behavioral strategy to reduce all-cause and cardiovascular mortality risk.