Changes in histone methylation status regulate chromatin structure and DNA-dependent processes such as transcription. Recent studies indicate that, analogous to other histone modifications, histone methylation is reversible. Retinoblastoma binding protein 2 (RBP2), a nuclear protein implicated in the regulation of transcription and differentiation by the retinoblastoma tumor suppressor protein, contains a JmjC domain recently defined as a histone demethylase signature motif. Here we report that RBP2 is a demethylase that specifically catalyzes demethylation on H3K4, whose methylation is normally associated with transcriptionally active genes. RBP2-/- mouse cells displayed enhanced transcription of certain cytokine genes, which, in the case of SDF1, was associated with increased H3K4 trimethylation. Furthermore, RBP2 specifically demethylated H3K4 in biochemical and cell-based assays. These studies provide mechanistic insights into transcriptional regulation by RBP2 and provide the first example of a mammalian enzyme capable of erasing trimethylated H3K4.