A defining feature of mitochondria is their maternal mode of inheritance. However, little is understood about the cellular mechanism through which paternal mitochondria, delivered from sperm, are eliminated from early mammalian embryos. Autophagy has been implicated in nematodes, but whether this mechanism is conserved in mammals has been disputed. Here, we show that cultured mouse fibroblasts and pre-implantation embryos use a common pathway for elimination of mitochondria. Both situations utilize mitophagy, in which mitochondria are sequestered by autophagosomes and delivered to lysosomes for degradation. The E3 ubiquitin ligases PARKIN and MUL1 play redundant roles in elimination of paternal mitochondria. The process is associated with depolarization of paternal mitochondria and additionally requires the mitochondrial outer membrane protein FIS1, the autophagy adaptor P62, and PINK1 kinase. Our results indicate that strict maternal transmission of mitochondria relies on mitophagy and uncover a collaboration between MUL1 and PARKIN in this process.