To cope with the reduced availability of O2 at high altitude, air-breathing vertebrates have evolved myriad adjustments in the cardiorespiratory system to match tissue O2 delivery with metabolic O2 demand. We explain how changes at interacting steps of the O2 transport pathway contribute to plastic and evolved changes in whole-animal aerobic performance under hypoxia. In vertebrates native to high altitude, enhancements of aerobic performance under hypoxia are attributable to a combination of environmentally induced and evolved changes in multiple steps of the pathway. Additionally, evidence suggests that many high-altitude natives have evolved mechanisms for attenuating maladaptive acclimatization responses to hypoxia, resulting in counter-gradient patterns of altitudinal variation for key physiological phenotypes. For traits that exhibit counteracting environmental and genetic effects, evolved changes in phenotype may be cryptic under field conditions and can only be revealed by rearing representatives of high- and low-altitude populations under standardized environmental conditions to control for plasticity.