The activating transcription factor-4 (ATF-4) is translationally induced under anoxic conditions, mediates part of the unfolded protein response following endoplasmic reticulum (ER) stress, and is a critical regulator of cell fate. Here, we identified the zipper II domain of ATF-4 to interact with the oxygen sensor prolyl-4-hydroxylase domain 3 (PHD3). The PHD inhibitors dimethyloxalylglycine (DMOG) and hypoxia, or proteasomal inhibition, all induced ATF-4 protein levels. Hypoxic induction of ATF-4 was due to increased protein stability, but was independent of the ubiquitin ligase von Hippel-Lindau protein (pVHL). A novel oxygen-dependent degradation (ODD) domain was identified adjacent to the zipper II domain. Mutations of 5 prolyl residues within this ODD domain or siRNA-mediated down-regulation of PHD3, but not of PHD2, was sufficient to stabilize ATF-4 under normoxic conditions. These data demonstrate that PHD-dependent oxygen-sensing recruits both the hypoxia-inducible factor (HIF) and ATF-4 systems, and hence not only confers adaptive responses but also cell fate decisions.