Epigenetic marks are reprogrammed in the gametes to reset genomic potential in the next generation. In mammals, paternal chromatin is extensively reprogrammed through the global erasure of DNA methylation and the exchange of histones with protamines1,2. Precisely how the paternal epigenome is reprogrammed in flowering plants has remained unclear since DNA is not demethylated and histones are retained in sperm3,4. Here, we describe a multi-layered mechanism by which H3K27me3 is globally lost from histone-based sperm chromatin in Arabidopsis. This mechanism involves the silencing of H3K27me3 writers, activity of H3K27me3 erasers and deposition of a sperm-specific histone, H3.10 (ref. 5), which we show is immune to lysine 27 methylation. The loss of H3K27me3 facilitates the transcription of genes essential for spermatogenesis and pre-configures sperm with a chromatin state that forecasts gene expression in the next generation. Thus, plants have evolved a specific mechanism to simultaneously differentiate male gametes and reprogram the paternal epigenome.