In the brain, increased neural activity is correlated with increases of cerebral blood flow and tissue oxygenation. However, how cerebral oxygen dynamics are controlled in the behaving animal remains unclear. We investigated to what extent cerebral oxygenation varies during locomotion. We measured oxygen levels in the cortex of awake, head-fixed mice during locomotion using polarography, spectroscopy, and two-photon phosphorescence lifetime measurements of oxygen sensors. We find that locomotion significantly and globally increases cerebral oxygenation, specifically in areas involved in locomotion, as well as in the frontal cortex and the olfactory bulb. The oxygenation increase persists when neural activity and functional hyperemia are blocked, occurred both in the tissue and in arteries feeding the brain, and is tightly correlated with respiration rate and the phase of respiration cycle. Thus, breathing rate is a key modulator of cerebral oxygenation and should be monitored during hemodynamic imaging, such as in BOLD fMRI.