In mammalian spermatozoa, most but not all of the genome is densely packaged by protamines. Here we reveal the molecular logic underlying the retention of nucleosomes in mouse spermatozoa, which contain only 1% residual histones. We observe high enrichment throughout the genome of nucleosomes at CpG-rich sequences that lack DNA methylation. Residual nucleosomes are largely composed of the histone H3.3 variant and are trimethylated at Lys4 of histone H3 (H3K4me3). Canonical H3.1 and H3.2 histones are also enriched at CpG-rich promoters marked by Polycomb-mediated H3K27me3, a modification predictive of gene repression in preimplantation embryos. Histone variant-specific nucleosome retention in sperm is strongly associated with nucleosome turnover in round spermatids. Our data show evolutionary conservation of the basic principles of nucleosome retention in mouse and human sperm, supporting a model of epigenetic inheritance by nucleosomes between generations.