Hydrogenosomes are H2-producing mitochondrial homologues found in some anaerobic microbial eukaryotes that provide a rare intracellular niche for H2-utilizing endosymbiotic archaea. Among ciliates, anaerobic and aerobic lineages are interspersed, demonstrating that the switch to an anaerobic lifestyle with hydrogenosomes has occurred repeatedly and independently. To investigate the molecular details of this transition we generated genomic and transcriptomic datasets from anaerobic ciliates representing three distinct lineages. Our data demonstrate that hydrogenosomes have evolved from ancestral mitochondria in each case and reveal different degrees of independent mitochondrial genome and proteome reductive evolution, including the first example of complete mitochondrial genome loss in ciliates. Intriguingly, the FeFe-hydrogenase used for generating H2 has a unique domain structure among eukaryotes and appears to have been present, potentially through a single lateral gene transfer from an unknown donor, in the common aerobic ancestor of all three lineages. The early acquisition and retention of FeFe-hydrogenase helps to explain the facility whereby mitochondrial function can be so radically modified within this diverse and ecologically important group of microbial eukaryotes.