Functional genomic elements are marked by characteristic DNA and histone modification signatures. How combinatorial chromatin modification states are recognized by epigenetic reader proteins and how this is linked to their biological function is largely unknown. Here we provide a detailed molecular analysis of chromatin recognition by the lysine demethylase KDM2A. Using biochemical approaches we identify a nucleosome interaction module within KDM2A consisting of a CXXC type zinc finger, a PHD domain and a newly identified Heterochromatin Protein 1 (HP1) interaction motif that mediates direct binding between KDM2A and HP1. This nucleosome interaction module enables KDM2A to decode nucleosomal H3K9me3 modification in addition to CpG methylation signals. The multivalent engagement with DNA and HP1 results in a nucleosome binding circuit in which KDM2A can be recruited to H3K9me3-modified chromatin through HP1, and HP1 can be recruited to unmodified chromatin by KDM2A. A KDM2A mutant deficient in HP1-binding is inactive in an in vivo overexpression assay in zebrafish embryos demonstrating that the HP1 interaction is essential for KDM2A function. Our results reveal a complex regulation of chromatin binding for both KDM2A and HP1 that is modulated by DNA- and H3K9-methylation, and suggest a direct role for KDM2A in chromatin silencing.