Histone lysine methylation can be removed by JmjC domain-containing proteins in a sequence- and methylation-state-specific manner. However, how substrate specificity is determined and how the enzymes are regulated were largely unknown. We recently found that ceKDM7A, a PHD- and JmjC domain-containing protein, is a histone demethylase specific for H3K9me2 and H3K27me2, and the PHD finger binding to H3K4me3 guides the demethylation activity in vivo. To provide structural insight into the molecular mechanisms for the enzymatic activity and the function of the PHD finger, we solved six crystal structures of the enzyme in apo form and in complex with single or two peptides containing various combinations of H3K4me3, H3K9me2, and H3K27me2 modifications. The structures indicate that H3K9me2 and H3K27me2 interact with ceKDM7A in a similar fashion, and that the peptide-binding specificity is determined by a network of specific interactions. The geometrical measurement of the structures also revealed that H3K4me3 associated with the PHD finger and H3K9me2 bound to the JmjC domain are from two separate molecules, suggesting a trans-histone peptide-binding mechanism. Thus, our systemic structural studies reveal not only the substrate recognition by the catalytic domain but also more importantly, the molecular mechanism of dual specificity of ceDKM7A for both H3K9me2 and H3K27me2.