The heterodimeric hypoxia-inducible transcription factors (HIFs) are central regulators of the response to low oxygenation. HIF-alpha subunits are constitutively expressed but rapidly degraded under normoxic conditions. Oxygen-dependent hydroxylation of two conserved prolyl residues by prolyl-4-hydroxylase domain-containing enzymes (PHDs) targets HIF-alpha for proteasomal destruction. We identified the peptidyl prolyl cis/trans isomerase FK506-binding protein 38 (FKBP38) as a novel interactor of PHD2. Yeast two-hybrid, glutathione S-transferase pull-down, coimmunoprecipitation, colocalization, and mammalian two-hybrid studies confirmed specific FKBP38 interaction with PHD2, but not with PHD1 or PHD3. PHD2 and FKBP38 associated with their N-terminal regions, which contain no known interaction motifs. Neither FKBP38 mRNA nor protein levels were regulated under hypoxic conditions or after PHD inhibition, suggesting that FKBP38 is not a HIF/PHD target. Stable RNA interference-mediated depletion of FKBP38 resulted in increased PHD hydroxylation activity and decreased HIF protein levels and transcriptional activity. Reconstitution of FKBP38 expression abolished these effects, which were independent of the peptidyl prolyl cis/trans isomerase activity. Downregulation of FKBP38 did not affect PHD2 mRNA levels but prolonged PHD2 protein stability, suggesting that FKBP38 is involved in PHD2 protein regulation.