Paternal contributions to epigenetic inheritance are not well understood. We report that in C. elegans sperm, the genome is packaged in nucleosomes and carries a histone-based epigenetic memory of gene expressions during spermatogenesis. In mature sperm, genes with spermatogenesis-specific expression are marked with both active and represseive histone modifications and genes with oogenesis-enriched expression are marked with active histone modifications. We showed that genes with oogenesis-enriched expression are in fact transcribed in spermatogenic germlines. We tested if sperm chromatin marking is necessary for germ cell development in offspring that inherit both sperm and oocyte chromosomes, using male parents that either can or cannot generate H3K27me3. Males homozygous for a mutation in mes-3, which encodes a member of the worm PRC2 complex, were mated with feminized mes-3/+ heterozygous worms to produce offspring that inherited sperm chromosomes lacking H3K27me3. We call these offspring M+P- or MpPm (Maternal chromosomes are + or plus for H3K27me3, Paternal chromosomes are - or minus for H3K27me3). Most of the resulting mes-3 homozygous M+P- offspring developed into sterile adults in this sensitized genetic background. In contrast, genetically identical control offspring that received appropriate H3K27me3-marked sperm chromosomes (M+P+ or MpPp) displayed low sterility. We compared genes mis-regulated in mes-3 male germlines versus control him-8 male germlines, mature sperm from those germlines, and germlines of mes-3 mutant F1 offspring that inherited sperm chromatin lacking H3K27me3 (M+P-) versus inherited sperm chromatin with H3K27me3 (M+P+), based on RNA-seq. Overall design: 1) Transcriptome profiles of male germlines (2 replicates from N2 wild-type males and 4 replicates from him-8 males) vs. oogenic germlines (3 replicates from N2 hermaphrodites and 3 replicates from fem-2 females). 2) mes-3 male germlines (3 replicates) vs. control him-8 male germlines (4 replicates), mes-3 sperm (3 replicates) vs. control him-8 sperm (3 replicates), and F1 M+P- germlines (2 replicates) vs. genetically identical F1 M+P+ germlines (2 replicates).