Both DNA methylation and post-translational histone modifications contribute to gene silencing, but the mechanistic relationship between these epigenetic marks is unclear. Mutations in two Arabidopsis genes, the KRYPTONITE (KYP) histone H3 lysine 9 (H3K9) methyltransferase and the CHROMOMETHYLASE3 (CMT3) DNA methyltransferase, cause a reduction of CNG DNA methylation, suggesting that H3K9 methylation controls CNG DNA methylation. Here we show that the chromodomain of CMT3 can directly interact with the N-terminal tail of histone H3, but only when it is simultaneously methylated at both the H3K9 and H3K27 positions. Furthermore, using chromatin immunoprecipitation analysis and immunohistolocalization experiments, we found that H3K27 methylation colocalizes with H3K9 methylation at CMT3-controlled loci. The H3K27 methylation present at heterochromatin was not affected by mutations in KYP or in several Arabidopsis PcG related genes including the Enhancer of Zeste homologs, suggesting that a novel pathway controls heterochromatic H3K27 methylation. Our results suggest a model in which H3K9 methylation by KYP, and H3K27 methylation by an unknown enzyme provide a combinatorial histone code for the recruitment of CMT3 to silent loci.