Mitochondrial DNA (mtDNA) has been proposed to be involved in respiratory function, and mtDNA mutations have been associated with aging, tumors, and various disorders, but the effects of mtDNA imported into transplants from different individuals or aged subjects have been unclear. We examined this issue by generating trans-mitochondrial tumor cells and embryonic stem cells that shared the syngenic C57BL/6 (B6) strain-derived nuclear DNA background but possessed mtDNA derived from allogenic mouse strains. We demonstrate that transplants with mtDNA from the NZB/B1NJ strain were rejected from the host B6 mice, not by the acquired immune system but by the innate immune system. This rejection was caused partly by NK cells and involved a MyD88-dependent pathway. These results introduce novel roles of mtDNA and innate immunity in tumor immunology and transplantation medicine.