Distinct lysine methylation marks on histones create dynamic signatures deciphered by the "effector" modules, although the underlying mechanisms remain unclear. We identified the plant homeodomain- and Jumonji C domain-containing protein PHF2 as a novel histone H3K9 demethylase. We show in biochemical and crystallographic analyses that PHF2 recognizes histone H3K4 trimethylation through its plant homeodomain finger and that this interaction is essential for PHF2 occupancy and H3K9 demethylation at rDNA promoters. Our study provides molecular insights into the mechanism by which distinct effector domains within a protein cooperatively modulate the "cross-talk" of histone modifications.