HIF is a transcriptional complex that plays a central role in mammalian oxygen homeostasis. Recent studies have defined posttranslational modification by prolyl hydroxylation as a key regulatory event that targets HIF-alpha subunits for proteasomal destruction via the von Hippel-Lindau ubiquitylation complex. Here, we define a conserved HIF-VHL-prolyl hydroxylase pathway in C. elegans, and use a genetic approach to identify EGL-9 as a dioxygenase that regulates HIF by prolyl hydroxylation. In mammalian cells, we show that the HIF-prolyl hydroxylases are represented by a series of isoforms bearing a conserved 2-histidine-1-carboxylate iron coordination motif at the catalytic site. Direct modulation of recombinant enzyme activity by graded hypoxia, iron chelation, and cobaltous ions mirrors the characteristics of HIF induction in vivo, fulfilling requirements for these enzymes being oxygen sensors that regulate HIF.