Cerebral hypoxic vasodilation is poorly understood in humans, which undermines the development of therapeutics to optimize cerebral oxygen delivery. Across four investigations (total n = 195) we investigated the role of nitric oxide (NO) and hemoglobin-based S-nitrosothiol (RSNO) and nitrite (NO2-) signaling in the regulation of cerebral hypoxic vasodilation. We conducted hemodilution (n = 10) and NO synthase inhibition experiments (n = 11) as well as hemoglobin oxygen desaturation protocols, wherein we measured cerebral blood flow (CBF), intra-arterial blood pressure, and in subsets of participants trans-cerebral release/uptake of RSNO and NO2-. Higher CBF during hypoxia was associated with greater trans-cerebral RSNO release but not NO2-, while NO synthase inhibition reduced cerebral hypoxic vasodilation. Hemodilution increased the magnitude of cerebral hypoxic vasodilation following acute hemodilution, while in 134 participants tested under normal conditions, hypoxic cerebral vasodilation was inversely correlated to arterial hemoglobin concentration. These studies were replicated in a sample of polycythemic high-altitude native Andeans suffering from excessive erythrocytosis (n = 40), where cerebral hypoxic vasodilation was inversely correlated to hemoglobin concentration, and improved with hemodilution (n = 6). Collectively, our data indicate that cerebral hypoxic vasodilation is partially NO-dependent, associated with trans-cerebral RSNO release, and place hemoglobin-based NO signaling as a central mechanism of cerebral hypoxic vasodilation in humans.