Histone methylation regulates chromatin structure and transcription. The recently identified histone demethylase lysine-specific demethylase 1 (LSD1) is chemically restricted to demethylation of only mono- and di- but not trimethylated histone H3 lysine 4 (H3K4me3). We show that the X-linked mental retardation (XLMR) gene SMCX (JARID1C), which encodes a JmjC-domain protein, reversed H3K4me3 to di- and mono- but not unmethylated products. Other SMCX family members, including SMCY, RBP2, and PLU-1, also demethylated H3K4me3. SMCX bound H3K9me3 via its N-terminal PHD (plant homeodomain) finger, which may help coordinate H3K4 demethylation and H3K9 methylation in transcriptional repression. Significantly, several XLMR-patient point mutations reduced SMCX demethylase activity and binding to H3K9me3 peptides, respectively. Importantly, studies in zebrafish and primary mammalian neurons demonstrated a role for SMCX in neuronal survival and dendritic development and a link to the demethylase activity. Our findings thus identify a family of H3K4me3 demethylases and uncover a critical link between histone modifications and XLMR.