The hypoxic response in humans is mediated by the hypoxia-inducible transcription factor (HIF), for which prolyl hydroxylases (PHDs) act as oxygen-sensing components. The evolutionary origins of the HIF system have been previously unclear. We demonstrate a functional HIF system in the simplest animal, Trichoplax adhaerens: HIF targets in T. adhaerens include glycolytic and metabolic enzymes, suggesting a role for HIF in the adaptation of basal multicellular animals to fluctuating oxygen levels. Characterization of the T. adhaerens PHDs and cross-species complementation assays reveal a conserved oxygen-sensing mechanism. Cross-genomic analyses rationalize the relative importance of HIF system components, and imply that the HIF system is likely to be present in all animals, but is unique to this kingdom.