In Arabidopsis, CHG DNA methylation is controlled by the H3K9 methylation mark through a self-reinforcing loop between DNA methyltransferase CHROMOMETHYLASE3 (CMT3) and H3K9 histone methyltransferase KRYPTONITE/SUVH4 (KYP). We report on the structure of KYP in complex with methylated DNA, substrate H3 peptide, and cofactor SAH, thereby defining the spatial positioning of the SRA domain relative to the SET domain. The methylated DNA is bound by the SRA domain with the 5mC flipped out of the DNA, while the H3(1-15) peptide substrate binds between the SET and post-SET domains, with the ε-ammonium of K9 positioned adjacent to bound SAH. These structural insights, complemented by functional data on key mutants of residues lining the 5mC and H3K9-binding pockets within KYP, establish how methylated DNA recruits KYP to the histone substrate. Together, the structures of KYP and previously reported CMT3 complexes provide insights into molecular mechanisms linking DNA and histone methylation.