X-linked mental retardation (XLMR) is an inherited disorder that mostly affects males and is caused by mutations in genes located on the X chromosome. Here, we show that the XLMR protein PHF8 and a C. elegans homolog F29B9.2 catalyze demethylation of di- and monomethylated lysine 9 of histone H3 (H3K9me2/me1). The PHD domain of PHF8 binds to H3K4me3 and colocalizes with H3K4me3 at transcription initiation sites. Furthermore, PHF8 interacts with another XMLR protein, ZNF711, which binds to a subset of PHF8 target genes, including the XLMR gene JARID1C. Of interest, the C. elegans PHF8 homolog is highly expressed in neurons, and mutant animals show impaired locomotion. Taken together, our results functionally link the XLMR gene PHF8 to two other XLMR genes, ZNF711 and JARID1C, indicating that MR genes may be functionally linked in pathways, causing the complex phenotypes observed in patients developing MR.