Protein stability of hypoxia-inducible factor (HIF) alpha subunits is regulated by the oxygen-sensing prolyl-4-hydroxylase domain (PHD) enzymes. When oxygen is abundant, HIFalpha subunits are hydroxylated and rapidly degraded; but when oxygen is scarce, HIFalpha subunits remain stable and form active heterodimeric HIF transcription factors which induce a large number of genes involved in adaptation to hypoxic conditions with physiological implications for erythropoiesis, angiogenesis, cardiovascular function and cellular metabolism. Oxygen-sensing is regulated by the co-substrate-dependent activity and hypoxia-inducible abundance of the PHD enzymes which trigger HIFalpha stability even under low oxygen conditions. Based on the subtle balance between PHD and HIFalpha levels/activities, these two factors form the core of a mutually adjusted, self-adaptive oxygen sensing system. A number of upstream regulators of the PHDs trigger this oxygen sensing system. Moreover, the recent identification of novel downstream targets of PHDs suggest that cellular oxygen sensing by PHDs governs the function of other signalling pathways, in addition to the HIF system.