Genetic studies have revealed that the antagonistic interplay between PcG and TrxG/MLL complexes is essential for the proper maintenance of vertebrate Hox gene expression in time and space. Hox genes must be silenced in totipotent embryonic stem cells and, in contrast, rapidly activated during embryogenesis. Here we discuss some recently published articles that propose a novel mechanism for the induction of Hox gene transcription. These studies report a new family of histone demethylases that remove H3K27me3/me2 repressive marks at Hox promoters during differentiation of stem cells. Though the overall importance of these enzymes for proper embryogenesis was demonstrated, their precise role in Hox gene epigenetic regulation during development still remains to be firmly established.