Reversible histone methylation and demethylation are highly regulated processes that are crucial for chromatin reorganization and regulation of gene transcription in response to extracellular conditions. However, the mechanisms that regulate histone-modifying enzymes are largely unknown. Here, we characterized a protein kinase A (PKA)-dependent histone lysine demethylase complex, PHF2-ARID5B. PHF2, a jmjC demethylase, is enzymatically inactive by itself, but becomes an active H3K9Me2 demethylase through PKA-mediated phosphorylation. We found that phosphorylated PHF2 then associates with ARID5B, a DNA-binding protein, and induce demethylation of methylated ARID5B. This modification leads to targeting of the PHF2-ARID5B complex to its target promoters, where it removes the repressive H3K9Me2 mark. These findings suggest that the PHF2-ARID5B complex is a signal-sensing modulator of histone methylation and gene transcription, in which phosphorylation of PHF2 enables subsequent formation of a competent and specific histone demethylase complex.