Abstract Background Complex organismal traits are often the result of multiple interacting genes and sub-organismal phenotypes, but how these interactions shape the evolutionary trajectories of adaptive traits is poorly understood. We examined how functional interactions between cardiorespiratory traits contribute to adaptive increases in the capacity for aerobic thermogenesis (maximal O2 consumption, V̇O2max, during acute cold exposure) in high-altitude deer mice (Peromyscus maniculatus). We crossed highland and lowland deer mice to produce F2 inter-population hybrids, which expressed genetically based variation in hemoglobin (Hb) O2 affinity on a mixed genetic background. We then combined physiological experiments and mathematical modeling of the O2 transport pathway to examine the links between cardiorespiratory traits and V̇O2max. Results Physiological experiments revealed that increases in Hb-O2 affinity of red blood cells improved blood oxygenation in hypoxia but were not associated with an enhancement in V̇O2max. Sensitivity analyses performed using mathematical modeling showed that the influence of Hb-O2 affinity on V̇O2max in hypoxia was contingent on the capacity for O2 diffusion in active tissues. Conclusions These results suggest that increases in Hb-O2 affinity would only have adaptive value in hypoxic conditions if concurrent with or preceded by increases in tissue O2 diffusing capacity. In high-altitude deer mice, the adaptive benefit of increasing Hb-O2 affinity is contingent on the capacity to extract O2 from the blood, which helps resolve controversies about the general role of hemoglobin function in hypoxia tolerance.