The origin of eukaryotes is a major open question in evolutionary biology. Multiple hypotheses posit that eukaryotes likely evolved from a syntrophic relationship between an archaeon and an alphaproteobacterium based on H2 exchange. However, there are no strong indications that modern eukaryotic H2 metabolism originated from archaea or alphaproteobacteria. Here, we present evidence for the origin of H2 metabolism genes in eukaryotes from an ancestor of the Anoxychlamydiales-a group of anaerobic chlamydiae, newly described here, from marine sediments. Among Chlamydiae, these bacteria uniquely encode genes for H2 metabolism and other anaerobiosis-associated pathways. Phylogenetic analyses of several components of H2 metabolism reveal that Anoxychlamydiales homologs are the closest relatives to eukaryotic sequences. We propose that an ancestor of the Anoxychlamydiales contributed these key genes during the evolution of eukaryotes, supporting a mosaic evolutionary origin of eukaryotic metabolism.