In mammals and other air-breathing vertebrates that live at high altitude, adjustments in convective O2 transport via changes in blood hemoglobin (Hb) content and/or Hb-O2 affinity can potentially mitigate the effects of arterial hypoxemia. However, there are conflicting views about the optimal values of such traits in hypoxia, partly due to the intriguing observation that hypoxia-induced acclimatization responses in humans and other predominantly lowland mammals are frequently not aligned in the same direction as evolved phenotypic changes in high-altitude natives. Here we review relevant theoretical and empirical results and we highlight experimental studies of rodents and humans that provide insights into the combination of hematological changes that help attenuate the decline in aerobic performance in hypoxia. For a given severity of hypoxia, experimental results suggest that optimal values for hematological traits are conditional on the states of other interrelated phenotypes that govern different steps in the O2-transport pathway.