The Myxozoa are oligo-cellular parasites with alternate hosts-fish and annelid worms-and some myxozoan species harm farmed fish. The phylum Myxozoa, comprising 2,100 species, was difficult to position in the tree of life, due to its fast evolutionary rate. Recent phylogenomic studies utilizing an extensive number of nuclear-encoded genes have confirmed that Myxozoans belong to Cnidaria. Nevertheless, the evolution of parasitism and extreme body simplification in Myxozoa is not well understood, and no myxozoan mitochondrial DNA sequence has been reported to date. To further elucidate the evolution of Myxozoa, we sequenced the mitochondrial genomes of the myxozoan species Kudoa septempunctata, K. hexapunctata and K. iwatai and compared them with those of other metazoans. The Kudoa mitochondrial genomes code for ribosomal RNAs, transfer RNAs, eight proteins for oxidative phosphorylation and three proteins of unknown function, and they are among the metazoan mitochondrial genomes coding the fewest proteins. The mitochondrial-encoded proteins were extremely divergent, exhibiting the fastest evolutionary rate in Metazoa. Nevertheless, the dN/dS ratios of the protein genes in genus Kudoa were approximately 0.1 and similar to other cnidarians, indicating that the genes are under negative selection. Despite the divergent genetic content, active oxidative phosphorylation was indicated by the transcriptome, metabolism and structure of mitochondria in K. septempunctata. As possible causes, we attributed the divergence to the population genetic characteristics shared between the two most divergent clades, Ctenophora and Myxozoa, and to the parasitic lifestyle of Myxozoa. The fast-evolving, functional mitochondria of the genus Kudoa expanded our understanding of metazoan mitochondrial evolution.