The heterochromatin of many eukaryotes is marked by both histone H3 lysine 9 (H3K9) methylation and DNA cytosine methylation. Several studies have revealed links between these two epigenetic markers. The molecular mechanisms involved in establishment of these links, however, remain largely unknown. In plants, H3K9 methylation is primarily carried out by a highly conserved family of proteins that contain SET and SRA (SET- and RING-associated) domains. Here, we show that the SRA-SET domain H3K9 methyltransferase NtSET1, as well as LIKE HETEROCHROMATIN PROTEIN1, binds heterochromatin DNA repeats. In the yeast two-hybrid assay, NtSET1 binds the DNA methylcytosine-binding protein VARIANT IN METHYLATION1 (VIM1), which contains conserved PHD, SRA and RING domains. This binding requires either the N-terminus of NtSET1 containing the SRA domain or the C-terminus of NtSET1 containing the SET domain and the PHD domain of VIM1. Consistent with a role in the establishment/maintenance of chromatin structure during cell division, VIM1 transcripts are abundant in actively dividing cells and the VIM1 protein is localized in the nucleus. While null vim1 mutant plants show a normal growth phenotype, transgenic Arabidopsis plants over-expressing VIM1 show inhibition in root growth and delay in flowering. We propose that SRA-SET domain H3K9 methyltransferases associate with the PHD-SRA-RING domain protein VIM1, mutually reinforcing H3K9 and DNA methylation in heterochromatinization.