Methylation of histone H3 lysine 27 (H3K27) is a posttranslational modification that is highly correlated with genomic silencing. Here we show that human UTX, a member of the Jumonji C family of proteins, is a di- and trimethyl H3K27 demethylase. UTX occupies the promoters of HOX gene clusters and regulates their transcriptional output by modulating the recruitment of polycomb repressive complex 1 and the monoubiquitination of histone H2A. Moreover, UTX associates with mixed-lineage leukemia (MLL) 2/3 complexes, and during retinoic acid signaling events, the recruitment of the UTX complex to HOX genes results in H3K27 demethylation and a concomitant methylation of H3K4. Our results suggest a concerted mechanism for transcriptional activation in which cycles of H3K4 methylation by MLL2/3 are linked with the demethylation of H3K27 through UTX.