Activation of hypoxia-inducible factors (HIF), responsible for tumor angiogenesis and glycolytic switch, is regulated by reduced oxygen availability. Normally, HIF-alpha proteins are maintained at low levels, controlled by site-specific hydroxylation carried out by HIF prolyl hydroxylases (PHD) and subsequent proteasomal degradation via the von Hippel-Lindau ubiquitin ligase. Using a yeast two-hybrid screen, we identified an interaction between melanoma antigen-11 (MAGE-11) cancer-testis antigen and the major HIF-alpha hydroxylating enzyme PHD2. The interaction was confirmed by a pull-down assay, coimmunoprecipitation, and colocalization in both normoxic and hypoxic conditions. Furthermore, MAGE-9, the closest homologue of MAGE-11, was also found to interact with PHD2. MAGE-11 inhibited PHD activity without affecting protein levels. This inhibition was accompanied by stabilization of ectopic or endogenous HIF-1alpha protein. Knockdown of MAGE-11 by small interfering RNA results in decreased hypoxic induction of HIF-1alpha and its target genes. Inhibition of PHD by MAGE-11, and following activation of HIFs, is a novel tumor-associated HIF regulatory mechanism. This finding provides new insights into the significance of MAGE expression in tumors and may provide valuable tools for therapeutic intervention because of the restricted expression of the MAGE gene family in cancers, but not in normal tissues.