In naïve CD8+T cells, bivalent histone modifications play an important role in both poising effector signature genes for an immediate response as well as constraining these genes to prevent transcriptional aberrancy. While the active histone modification, H3K4me3 is stably maintained at these effector gene targets, we showed that demethylation of the repressive histone modification, H3K27me3 is an obligatory step during effector CD8+ T cells differentiation. Despite its highly dynamic pattern, we found that H3K27me3 removal was evident within early hours of T cell activation and these regions remained demethylated even throughout differentiation into effector and memory T cells. Enriched in key T cell-specific transcription factor motifs, these regions often belong to genes involved in a broad number of cellular support processes. Perturbing this demethylation process in vivo functionally reduced the cells’ ability to divide efficiently but most importantly, it hindered the formation of effector and distinct memory CD8+ T cell populations. These findings highlight that naïve CD8+ T cells experience a series of step-wise progression within early T cell hour activation. H3K27me3 demethylation therefore represents a novel regulatory step that relieves the epigenetic restraint in naïve CD8+ T cells. By controlling cellular support processes, the immediate removal of H3K27me3 has direct consequence on the fate decision between effector and memory CD8+ T cell lineages.