DNMT3 proteins are de novo DNA methyltransferases that are responsible for the establishment of DNA methylation patterns in mammalian genomes. Here, we have determined the crystal structures of the ATRX-DNMT3-DNMT3L (ADD) domain of DNMT3A in an unliganded form and in a complex with the amino-terminal tail of histone H3. Combined with the results of biochemical analysis, the complex structure indicates that DNMT3A recognizes the unmethylated state of lysine 4 in histone H3. This finding indicates that the recruitment of DNMT3A onto chromatin, and thereby de novo DNA methylation, is mediated by recognition of the histone modification state by its ADD domain. Furthermore, our biochemical and nuclear magnetic resonance data show mutually exclusive binding of the ADD domain of DNMT3A and the chromodomain of heterochromatin protein 1alpha to the H3 tail. These results indicate that de novo DNA methylation by DNMT3A requires the alteration of chromatin structure.