On the histone H3 tail, Lys 9 and Lys 27 are both methylation sites associated with epigenetic repression, and reside within a highly related sequence motif ARKS. Here we show that the chromodomain proteins Polycomb (Pc) and HP1 (heterochromatin protein 1) are highly discriminatory for binding to these sites in vivo and in vitro. In Drosophila S2 cells, and on polytene chromosomes, methyl-Lys 27 and Pc are both excluded from areas that are enriched in methyl-Lys 9 and HP1. Swapping of the chromodomain regions of Pc and HP1 is sufficient for switching the nuclear localization patterns of these factors, indicating a role for their chromodomains in both target site binding and discrimination. To better understand the molecular basis for the selection of methyl-lysine binding sites, we solved the 1.8 A structure of the Pc chromodomain in complex with a H3 peptide bearing trimethyl-Lys 27, and compared it with our previously determined structure of the HP1 chromodomain in complex with a H3 peptide bearing trimethyl-Lys 9. The Pc chromodomain distinguishes its methylation target on the H3 tail via an extended recognition groove that binds five additional residues preceding the ARKS motif.