Background Cardiorespiratory fitness may moderate the association between obesity and all‐cause mortality (ie, the “fat‐but‐fit” hypothesis), but unaddressed sources of bias are a concern. Methods and Results Cardiorespiratory fitness was estimated as watts per kilogram from a submaximal bicycle test in 77 169 men and women from the UK Biobank cohort and combined with World Health Organization standard body mass index categories, yielding 9 unique fitness‐fatness combinations. We also formed fitness‐fatness combinations based on bioimpedance as a direct measure of body composition. All‐cause mortality was ascertained from death registries. Multivariable‐adjusted Cox regression models were used to estimate hazard ratios and 95% CIs. We examined the association between fitness‐fatness combinations and all‐cause mortality in models with progressively more conservative approaches for accounting for reverse causation, misclassification of body composition, and confounding. Over a median follow‐up of 7.7 years, 1731 participants died. In our base model, unfit men and women had higher risk of premature mortality irrespective of levels of adiposity, compared with the normal weight–fit reference. This pattern was attenuated but maintained with more conservative approaches in men, but not in women. In analysis stratified by sex and excluding individuals with prevalent major chronic disease and short follow‐up and using direct measures of body composition, mortality risk was 1.78 (95% CI, 1.17–2.71) times higher in unfit‐obese men but not higher in obese‐fit men (0.94 [95% CI, 0.60–1.48]). In contrast, there was no increased risk in obese‐unfit women (1.09 [95% CI, 0.44–1.05]) as compared with the reference. Conclusions Cardiorespiratory fitness modified the association between obesity and mortality in men, but this pattern appeared susceptible to biases in women.