Polycomb response elements (PREs) are specific cis-regulatory sequences needed for transcriptional repression of HOX and other target genes by Polycomb group (PcG) proteins. Among the many PcG proteins known in Drosophila, Pho is the only sequence-specific DNA-binding protein. To gain insight into the function of Pho, we purified Pho protein complexes from Drosophila embryos and found that Pho exists in two distinct protein assemblies: a Pho-dINO80 complex containing the Drosophila INO80 nucleosome-remodeling complex, and a Pho-repressive complex (PhoRC) containing the uncharacterized gene product dSfmbt. Analysis of PhoRC reveals that dSfmbt is a novel PcG protein that is essential for HOX gene repression in Drosophila. PhoRC is bound at HOX gene PREs in vivo, and this targeting strictly depends on Pho-binding sites. Characterization of dSfmbt protein shows that its MBT repeats have unique discriminatory binding activity for methylated lysine residues in histones H3 and H4; the MBT repeats bind mono- and di-methylated H3-K9 and H4-K20 but fail to interact with these residues if they are unmodified or tri-methylated. Our results establish PhoRC as a novel Drosophila PcG protein complex that combines DNA-targeting activity (Pho) with a unique modified histone-binding activity (dSfmbt). We propose that PRE-tethered PhoRC selectively interacts with methylated histones in the chromatin flanking PREs to maintain a Polycomb-repressed chromatin state.