The low O2 experienced at high altitude is a significant challenge to effective aerobic locomotion, as it requires sustained tissue O2 delivery in addition to the appropriate allocation of metabolic substrates. Here, we tested whether high- and low-altitude deer mice ( Peromyscus maniculatus) have evolved different acclimation responses to hypoxia with respect to muscle metabolism and fuel use during submaximal exercise. Using F1 generation high- and low-altitude deer mice that were born and raised in common conditions, we assessed 1) fuel use during exercise, 2) metabolic enzyme activities, and 3) gene expression for key transporters and enzymes in the gastrocnemius. After hypoxia acclimation, highland mice showed a significant increase in carbohydrate oxidation and higher relative reliance on this fuel during exercise at 75% maximal O2 consumption. Compared with lowland mice, highland mice had consistently higher activities of oxidative and fatty acid oxidation enzymes in the gastrocnemius. In contrast, only after hypoxia acclimation did activities of hexokinase increase significantly in the muscle of highland mice to levels greater than lowland mice. Highland mice also responded to acclimation with increases in muscle gene expression for hexokinase 1 and 2 genes, whereas both populations increased mRNA expression for glucose transporters. Changes in skeletal muscle with acclimation suggest that highland mice had an increased capacity for the uptake and oxidation of circulatory glucose. Our results demonstrate that highland mice have evolved a distinct mode of hypoxia acclimation that involves an increase in carbohydrate use during exercise.