The length of gestation can affect offspring health and performance. Both maternal and fetal effects contribute to gestation length; however, paternal contributions to gestation length remain elusive. Using genome-wide association study (GWAS) in 27,214 Holstein bulls with millions of gestation records, here we identify nine paternal genomic loci associated with cattle gestation length. We demonstrate that these GWAS signals are enriched in pathways relevant to embryonic development, and in differentially methylated regions between sperm samples with long and short gestation length. We reveal that gestation length shares genetic and epigenetic architecture in sperm with calving ability, body depth, and conception rate. While several candidate genes are detected in our fine-mapping analysis, we provide evidence indicating ZNF613 as a promising candidate for cattle gestation length. Collectively, our findings support that the paternal genome and epigenome can impact gestation length potentially through regulation of the embryonic development.