Sperm-packaged DNA must undergo extensive reorganization to ensure its timely participation in embryonic mitosis. Whereas maternal control over this remodeling is well described, paternal contributions are virtually unknown. In this study, we show that Drosophila melanogaster males lacking Heterochromatin Protein 1E (HP1E) sire inviable embryos that undergo catastrophic mitosis. In these embryos, the paternal genome fails to condense and resolve into sister chromatids in synchrony with the maternal genome. This delay leads to a failure of paternal chromosomes, particularly the heterochromatin-rich sex chromosomes, to separate on the first mitotic spindle. Remarkably, HP1E is not inherited on mature sperm chromatin. Instead, HP1E primes paternal chromosomes during spermatogenesis to ensure faithful segregation post-fertilization. This transgenerational effect suggests that maternal control is necessary but not sufficient for transforming sperm DNA into a mitotically competent pronucleus. Instead, paternal action during spermiogenesis exerts post-fertilization control to ensure faithful chromosome segregation in the embryo.