X-chromosome inactivation (XCI) is established in two waves during mouse development. First, silencing of the paternal X chromosome (Xp) is triggered, with transcriptional repression of most genes and enrichment of epigenetic marks such as H3K27me3 being achieved in all cells by the early blastocyst stage. XCI is then reversed in the inner cell mass (ICM), followed by a second wave of maternal or paternal XCI, in the embryo-proper. Although the role of Xist RNA in triggering XCI is now clear, the mechanisms underlying Xp reactivation in the inner cell mass have remained enigmatic. Here we use in vivo single cell approaches (allele-specific RNAseq, nascent RNA FISH and immunofluorescence) and find that different genes show very different timing of reactivation. We observe that the genes reactivate at different stages and that initial enrichment in H3K27me3 anti-correlates with the speed of reactivation. To define whether this repressive histone mark is lost actively or passively, we investigate embryos mutant for the X-encoded H3K27me3 demethylase, UTX. Xp genes that normally reactivate slowly are retarded in their reactivation in Utx mutants, while those that reactive rapidly are unaffected. Therefore, efficient reprogramming of some X-linked genes in the inner cell mass is very rapid, indicating minimal epigenetic memory and potentially driven by transcription factors, whereas others may require active erasure of chromatin marks such as H3K27me3.