Hypoxia is a common feature of solid tumors. Prolyl hydroxylase enzymes (PHD1–3) are molecular oxygen sensors that regulate hypoxia-inducible factor activity, but their functions in metastatic disease remain unclear. Here, we assessed the significance of PHD enzymes during the metastatic spread of colorectal cancer. PHD expression analysis in 124 colorectal cancer patients revealed that reduced tumoral expression of PHD3 correlated with increased frequency of distant metastases and poor outcome. Tumorigenicity and metastatic potential of colorectal tumor cells over and underexpressing PHD3 were investigated in orthotopic and heterotopic tumor models. PHD3 overexpression in a syngeneic tumor model resulted in fewer liver metastases, whereas PHD3 knockdown induced tumor spread. The migration of PHD3-overexpressing tumor cells was also attenuated in vitro. Conversely, migratory potential and colony formation were enhanced in PHD3-deficient cells, and this phenotype was associated with enhanced mitochondrial ATP production. Furthermore, the effects of PHD3 deficiency were accompanied by increased mitochondrial expression of the BCL-2 family member, member myeloid cell leukemia sequence 1 (MCL-1), and could be reversed by simultaneous inhibition of MCL-1. MCL-1 protein expression was likewise enhanced in human colorectal tumors expressing low levels of PHD3. Therefore, we demonstrate that downregulation of PHD3 augments metastatic spread in human colorectal cancer and identify MCL-1 as a novel downstream effector of oxygen sensing. Importantly, these findings offer new insight into the possible, context-specific deleterious effects of pharmacologic PHD inhibition. Cancer Res; 76(8); 2219–30. ©2016 AACR.