N(ε)-Methylations of histone lysine residues play critical roles in cell biology by "marking" chromatin for transcriptional activation or repression. Lysine demethylases reverse N(ε)-methylation in a sequence- and methylation-selective manner. The determinants of sequence selectivity for histone demethylases have been unclear. The human JMJD2 (KDM4) H3K9 and H3K36 demethylases can be divided into members that act on both H3K9 and H3K36 and H3K9 alone. Kinetic, crystallographic, and mutagenetic studies in vitro and in cells on KDM4A-E reveal that selectivity is determined by multiple interactions within the catalytic domain but outside the active site. Structurally informed phylogenetic analyses reveal that KDM4A-C orthologues exist in all genome-sequenced vertebrates with earlier animals containing only a single KDM4 enzyme. KDM4D orthologues only exist in eutherians (placental mammals) where they are conserved, including proposed substrate sequence-determining residues. The results will be useful for the identification of inhibitors for specific histone demethylases.