While bar-headed geese are renowned for migration at high altitude over the Himalayas, previous work on captive birds suggested that these geese are unable to maintain rates of oxygen consumption while running in severely hypoxic conditions. To investigate this paradox, we re-examined the running performance and heart rates of bar-headed geese and barnacle geese (a low altitude species) during exercise in hypoxia. Bar-headed geese (n = 7) were able to run at maximum speeds (determined in normoxia) for 15 minutes in severe hypoxia (7% O2; simulating the hypoxia at 8500 m) with mean heart rates of 466±8 beats min−1. Barnacle geese (n = 10), on the other hand, were unable to complete similar trials in severe hypoxia and their mean heart rate (316 beats.min−1) was significantly lower than bar-headed geese. In bar-headed geese, partial pressures of oxygen and carbon dioxide in both arterial and mixed venous blood were significantly lower during hypoxia than normoxia, both at rest and while running. However, measurements of blood lactate in bar-headed geese suggested that anaerobic metabolism was not a major energy source during running in hypoxia. We combined these data with values taken from the literature to estimate (i) oxygen supply, using the Fick equation and (ii) oxygen demand using aerodynamic theory for bar-headed geese flying aerobically, and under their own power, at altitude. This analysis predicts that the maximum altitude at which geese can transport enough oxygen to fly without environmental assistance ranges from 6,800 m to 8,900 m altitude, depending on the parameters used in the model but that such flights should be rare.