Local vasodilation in response to hypoxia is a fundamental physiologic response ensuring oxygen delivery to tissues under metabolic stress. Recent studies identify a role for the red blood cell (RBC), with hemoglobin the hypoxic sensor. Herein, we investigate the mechanisms regulating this process and explore the relative roles of adenosine triphosphate, S-nitrosohemoglobin, and nitrite as effectors. We provide evidence that hypoxic RBCs mediate vasodilation by reducing nitrite to nitric oxide (NO) and ATP release. NO dependence for nitrite-mediated vasodilation was evidenced by NO gas formation, stimulation of cGMP production, and inhibition of mitochondrial respiration in a process sensitive to the NO scavenger C-PTIO. The nitrite reductase activity of hemoglobin is modulated by heme deoxygenation and heme redox potential, with maximal activity observed at 50% hemoglobin oxygenation (P₅₀). Concomitantly, vasodilation is initiated at the P₅₀, suggesting that oxygen sensing by hemoglobin is mechanistically linked to nitrite reduction and stimulation of vasodilation. Mutation of the conserved β93cys residue decreases the heme redox potential (ie, decreases E_1/2), an effect that increases nitrite reductase activity and vasodilation at any given hemoglobin saturation. These data support a function for RBC hemoglobin as an allosterically and redox-regulated nitrite reductase whose “enzyme activity” couples hypoxia to increased NO-dependent blood flow.