Abstract PRL-3, an oncogenic dual-specificity phosphatase, is overexpressed in 50% of acute myelogenous leukemia (AML) and associated with poor survival. We found that stable expression of PRL-3 confers cytokine independence and growth advantage of AML cells. However, how PRL-3 mediates these functions in AML is not known. To comprehensively screen for PRL3-regulated proteins in AML, we performed SILAC-based quantitative proteomics analysis and discovered 398 significantly perturbed proteins after PRL-3 overexpression. We show that Leo1, a component of RNA polymerase II–associated factor (PAF) complex, is a novel and important mediator of PRL-3 oncogenic activities in AML. We described a novel mechanism where elevated PRL-3 protein increases JMJD2C histone demethylase occupancy on Leo1 promoter, thereby reducing the H3K9me3 repressive signals and promoting Leo1 gene expression. Furthermore, PRL-3 and Leo1 levels were positively associated in AML patient samples (N = 24; P < 0.01). On the other hand, inhibition of Leo1 reverses PRL-3 oncogenic phenotypes in AML. Loss of Leo1 leads to destabilization of the PAF complex and downregulation of SOX2 and SOX4, potent oncogenes in myeloid transformation. In conclusion, we identify an important and novel mechanism by which PRL-3 mediates its oncogenic function in AML. Cancer Res; 74(11); 3043–53. ©2014 AACR.