Mitochondrial respiration is an ancient characteristic of eukaryotes. However, it was lost independently in multiple eukaryotic lineages as part of adaptations to an anaerobic lifestyle. We show that a similar adaptation occurred in a member of the Myxozoa, a large group of microscopic parasitic animals that are closely related to jellyfish and hydroids. Using deep sequencing approaches supported by microscopic observations, we present evidence that an animal has lost its mitochondrial genome. The myxozoan cells retain structures deemed mitochondrion-related organelles, but have lost genes related to aerobic respiration and mitochondrial genome replication. Our discovery shows that aerobic respiration, one of the most important metabolic pathways, is not ubiquitous among animals.