The hypoxia-inducible factors are α,β-heterodimeric transcription factors that mediate the chronic response to hypoxia in humans and other animals. Protein hydroxylases belonging to two different structural subfamilies of the Fe(II) and 2-oxoglutarate (2OG)-dependent oxygenase superfamily modify HIFα. HIFα prolyl-hydroxylation, as catalysed by the PHDs, regulates HIFα levels and, consequently, α,β-HIF levels. HIFα asparaginyl-hydroxylation, as catalysed by factor inhibiting HIF (FIH), regulates the transcriptional activity of α,β-HIF. The activities of the PHDs and FIH are regulated by O2 availability, enabling them to act as hypoxia sensors. We provide an overview of the biochemistry of the HIF hydroxylases, discussing evidence that their kinetic and structural properties may be tuned to their roles in the HIF system. Avenues for future research and therapeutic modulation are discussed.