The paternal environment has been linked to infertility and negative outcomes. Such effects may be transmitted via sperm through histone modifications. To date, in-depth profiling of the sperm chromatin in men has been limited. Here, we use deep sequencing to characterize the sperm profiles of histone H3 lysine 4 tri-methylation (H3K4me3) and DNA methylation in a representative reference population of 37 men. Our analysis reveals that H3K4me3 is localized throughout the genome and at genes for fertility and development. Remarkably, enrichment is also found at regions that escape epigenetic reprogramming in primordial germ cells, embryonic enhancers, and short-interspersed nuclear elements (SINEs). There is significant overlap in H3K4me3 and DNA methylation throughout the genome, suggesting a potential interplay between these marks previously reported to be mutually exclusive in sperm. Comparisons made between H3K4me3 marked regions in sperm and the embryonic transcriptome suggest an influence of paternal chromatin on embryonic gene expression.