Many anaerobic microbial parasites possess highly modified mitochondria known as mitochondrion-related organelles (MROs). The best-studied of these are the hydrogenosomes of Trichomonas vaginalis and Spironucleus salmonicida, which produce ATP anaerobically through substrate-level phosphorylation with concomitant hydrogen production; and the mitosomes of Giardia intestinalis, which are functionally reduced and lack any role in ATP production. However, to understand the metabolic specializations that these MROs underwent in adaptation to parasitism, data from their free-living relatives are needed. Here, we present a large-scale comparative transcriptomic study of MROs across a major eukaryotic group, Metamonada, examining lineage-specific gain and loss of metabolic functions in the MROs of Trichomonas, Giardia, Spironucleus and their free-living relatives. Our analyses uncover a complex history of ATP production machinery in diplomonads such as Giardia, and their closest relative, Dysnectes; and a correlation between the glycine cleavage machinery and lifestyles. Our data further suggest the existence of a previously undescribed biochemical class of MRO that generates hydrogen but is incapable of ATP synthesis.