Posttranslational modifications of histones regulate chromatin structure and gene expression. Histone demethylases, members of a newly emerging transcription-factor family, remove methyl groups from the lysine residues of the histone tails and thereby regulate the transcriptional activity of target genes. JmjC-domain-containing proteins have been predicted to be demethylases. For example, the JmjC-containing protein JMJD2A has been characterized as a H3-K9me3- and H3-K36me3-specific demethylase. Here, structures of the catalytic-core domain of JMJD2A with and without alpha-ketoglutarate in the presence of Fe2+ have been determined by X-ray crystallography. The structure of the core domain, consisting of the JmjN domain, the JmjC domain, the C-terminal domain, and a zinc-finger motif, revealed the unique elements that form a potential substrate binding pocket. Sited-directed mutagenesis in conjunction with demethylase activity assays allowed us to propose a molecular model for substrate selection by the JMJD2 histone demethylase family.