Mutations of human PHF8 cluster within its JmjC encoding exons and are linked to mental retardation (MR) and a cleft lip/palate phenotype. Sequence comparisons, employing structural insights, suggest that PHF8 contains the double stranded beta-helix fold and ferrous iron binding residues that are present in 2-oxoglutarate-dependent oxygenases. We report that recombinant PHF8 is an Fe(II) and 2-oxoglutarate-dependent N(epsilon)-methyl lysine demethylase, which acts on histone substrates. PHF8 is selective in vitro for N(epsilon)-di- and mono-methylated lysine residues and does not accept trimethyl substrates. Clinically observed mutations to the PHF8 gene cluster in exons encoding for the double stranded beta-helix fold and will therefore disrupt catalytic activity. The PHF8 missense mutation c.836C>T is associated with mild MR, mild dysmorphic features, and either unilateral or bilateral cleft lip and cleft palate in two male siblings. This mutant encodes a F279S variant of PHF8 that modifies a conserved hydrophobic region; assays with both peptides and intact histones reveal this variant to be catalytically inactive. The dependence of PHF8 activity on oxygen availability is interesting because the occurrence of fetal cleft lip has been demonstrated to increase with maternal hypoxia in mouse studies. Cleft lip and other congenital anomalies are also linked indirectly to maternal hypoxia in humans, including from maternal smoking and maternal anti-hypertensive treatment. Our results will enable further studies aimed at defining the molecular links between developmental changes in histone methylation status, congenital disorders and MR.