To maintain genome stability, cells pack large portions of their genome into silent chromatin or heterochromatin. Histone H3 lysine 9 methylation, a hallmark of heterochromatin, is recognized by conserved readers called chromodomains. But how chromodomains interact with their actual binding partner, the H3K9 methylated nucleosome, remains elusive. We have determined the structure of a nucleosome trimethylated at lysine 9 of histone H3 (H3K9me3 Nucleosome) in a complex with the chromodomain of Chp1, a protein required for RNA interference-dependent heterochromatin formation in fission yeast. The cryo-electron microscopy structure reveals that the chromodomain of Chp1 binds the histone H3 lysine 9 methylated tail and the core of the nucleosome, primarily histones H3 and H2B. Mutations in chromodomain of Chp1 loops, which interact with the nucleosome core, abolished this interaction in vitro. Moreover, fission yeast cells with Chp1 loop mutations have a defect in Chp1 recruitment and heterochromatin formation. This study reveals the structural basis for heterochromatic silencing and suggests that chromodomains could read histone code in the H3 tail and the nucleosome core, which would provide an additional layer of regulation.