Polycomb (PcG) and Trithorax (TrxG) group proteins act antagonistically to establish tissue-specific patterns of gene expression. The PcG protein Ezh2 facilitates repression by catalysing histone H3-Lys27 trimethylation (H3K27me3). For expression, H3K27me3 marks are removed and replaced by TrxG protein catalysed histone H3-Lys4 trimethylation (H3K4me3). Although H3K27 demethylases have been identified, the mechanism by which these enzymes are targeted to specific genomic regions to remove H3K27me3 marks has not been established. Here, we demonstrate a two-step mechanism for UTX-mediated demethylation at muscle-specific genes during myogenesis. Although the transactivator Six4 initially recruits UTX to the regulatory region of muscle genes, the resulting loss of H3K27me3 marks is limited to the region upstream of the transcriptional start site. Removal of the repressive H3K27me3 mark within the coding region then requires RNA Polymerase II (Pol II) elongation. Interestingly, blocking Pol II elongation on transcribed genes leads to increased H3K27me3 within the coding region, and formation of bivalent (H3K27me3/ H3K4me3) chromatin domains. Thus, removal of repressive H3K27me3 marks by UTX occurs through targeted recruitment followed by spreading across the gene.