For a long time, it has been assumed that the only role of sperm at fertilization is to introduce the male genome into the egg. Recently, ideas have emerged that the epigenetic state of the sperm nucleus could influence transcription in the embryo. However, conflicting reports have challenged the existence of epigenetic marks on sperm genes, and there are no functional tests supporting the role of sperm epigenetic marking on embryonic gene expression. Here, we show that sperm is epigenetically programmed to regulate embryonic gene expression. By comparing the development of sperm- and spermatid-derived frog embryos, we show that the programming of sperm for successful development relates to its ability to regulate transcription of a set of developmentally important genes. During spermatid maturation into sperm, these genes lose H3K4me2/3 and retain H3K27me3 marks. Experimental removal of these epigenetic marks at fertilization de-regulates gene expression in the resulting embryos in a paternal chromatin-dependent manner. This demonstrates that epigenetic instructions delivered by the sperm at fertilization are required for correct regulation of gene expression in the future embryos. The epigenetic mechanisms of developmental programming revealed here are likely to relate to the mechanisms involved in transgenerational transmission of acquired traits. Understanding how parental experience can influence development of the progeny has broad potential for improving human health.