Hypoxia-inducible factor (HIF) is a transcriptional complex that plays a central role in the regulation of gene expression by oxygen. In oxygenated and iron replete cells, HIF-α subunits are rapidly destroyed by a mechanism that involves ubiquitylation by the von Hippel–Lindau tumor suppressor (pVHL) E3 ligase complex. This process is suppressed by hypoxia and iron chelation, allowing transcriptional activation. Here we show that the interaction between human pVHL and a specific domain of the HIF-1α subunit is regulated through hydroxylation of a proline residue (HIF-1α P564) by an enzyme we have termed HIF-α prolyl-hydroxylase (HIF-PH). An absolute requirement for dioxygen as a cosubstrate and iron as cofactor suggests that HIF-PH functions directly as a cellular oxygen sensor.