Histone methylation is a dynamic process that participates in a diverse array of cellular processes and has been found to associate with cancer. Recently, several histone demethylases have been identified that catalyze the removal of methylation from histone H3 lysine residues. Through bioinformatic and biochemical analysis, we identified JARID1B as a H3K4 demethylase. Overexpression of JARID1B resulted in loss of tri-, di-, and monomethyl H3K4 but did not affect other histone lysine methylations. In vitro biochemical experiments demonstrated that JARID1B directly catalyzes the demethylation. The enzymatic activity requires the JmjC domain and uses Fe(II) and alpha-ketoglutarate as cofactors. Furthermore, we found that JARID1B is up-regulated in prostate cancer tissues, compared with benign prostate samples. We also demonstrated that JARID1B associates with androgen receptor and regulates its transcriptional activity. Thus, we identified JARID1B as a demethylase capable of removing three methyl groups from histone H3 lysine 4 and up-regulated in prostate cancer.