UHRF1 is an important epigenetic regulator connecting DNA methylation and histone methylations. UHRF1 is required for maintenance of DNA methylation through recruiting DNMT1 to DNA replication forks. Recent studies have shown that the plant homeodomain (PHD) of UHRF1 recognizes the N terminus of unmodified histone H3, and the interaction is inhibited by methylation of H3R2, whereas the tandem tudor domain (TTD) of UHRF1 recognizes trimethylated histone H3 lysine 9 (H3K9me3). However, how the two domains of UHRF1 coordinately recognize histone methylations remains elusive. In this report, we identified that PHD largely enhances the interaction between TTD and H3K9me3. We present the crystal structure of UHRF1 containing both TTD and PHD (TTD-PHD) in complex with H3K9m3 peptide at 3.0 Å resolution. The structure shows that TTD-PHD binds to the H3K9me3 peptide with 1:1 stoichiometry with the two domains connected by the H3K9me3 peptide and a linker region. The TTD interacts with residues Arg-8 and trimethylated Lys-9, and the PHD interacts with residues Ala-1, Arg-2, and Lys-4 of the H3K9me3 peptide. The biochemical experiments indicate that PHD-mediated recognition of unmodified H3 is independent of the TTD, whereas TTD-mediated recognition of H3K9me3 PHD. Thus, both TTD and PHD are essential for specific recognition of H3K9me3 by UHRF1. Interestingly, the H3K9me3 peptide induces conformational changes of TTD-PHD, which do not affect the autoubiquitination activity or hemimethylated DNA binding affinity of UHRF1 in vitro. Taken together, our studies provide structural insight into the coordinated recognition of H3K9me3 by the TTD and PHD of UHRF1.