Histone lysine methylation is a dynamic process that plays an important role in regulating chromatin structure and gene expression. Recent studies have identified Jhd2, a JmjC domain-containing protein, as an H3K4-specific demethylase in budding yeast. However, important questions regarding the regulation and functions of Jhd2 remain unanswered. In this study, we show that Jhd2 has intrinsic activity to remove all three states of H3K4 methylation in vivo and can dynamically associate with chromatin to modulate H3K4 methylation levels on both active and repressed genes and at the telomeric regions. We found that the plant homeodomain (PHD) finger of Jhd2 is important for its chromatin association in vivo. However, this association is not dependent on H3K4 methylation and the H3 N-terminal tail, suggesting the presence of an alternative mechanism by which Jhd2 binds nucleosomes. We also provide evidence that the JmjN domain and its interaction with the JmjC catalytic domain are important for Jhd2 function and that Not4 (an E3 ligase) monitors the structural integrity of this interdomain interaction to maintain the overall protein levels of Jhd2. We show that the S451R mutation in human SMCX (a homolog of Jhd2), which has been linked to mental retardation, and the homologous T359R mutation in Jhd2 affect the protein stability of both of these proteins. Therefore, our findings provide a mechanistic explanation for the observed defects in patients harboring this SMCX mutant and suggest the presence of a conserved pathway involving Not4 that modulates the protein stability of both yeast Jhd2 and human SMCX.