Hypoxia-inducible factor-1 (HIF-1) is a transcriptional complex that controls cellular and systemic homeostatic responses to oxygen availability. HIF-1α is the oxygen-regulated subunit of HIF-1, an αβ heterodimeric complex. HIF-1α is stable in hypoxia, but in the presence of oxygen it is targeted for proteasomal degradation by the ubiquitination complex pVHL, the protein of the von Hippel–Lindau (VHL) tumour suppressor gene and a component of an E3 ubiquitin ligase complex^,. Capture of HIF-1α by pVHL is regulated by hydroxylation of specific prolyl residues in two functionally independent regions of HIF-1α^,,,. The crystal structure of a hydroxylated HIF-1α peptide bound to VCB (pVHL, elongins C and B) and solution binding assays reveal a single, conserved hydroxyproline-binding pocket in pVHL. Optimized hydrogen bonding to the buried hydroxyprolyl group confers precise discrimination between hydroxylated and unmodified prolyl residues. This mechanism provides a new focus for development of therapeutic agents to modulate cellular responses to hypoxia.