Breviatea form a lineage of free living, unicellular protists, distantly related to animals and fungi1,2. This lineage emerged almost one billion years ago, when the oceanic oxygen content was low, and extant Breviatea have evolved or retained an anaerobic lifestyle3,4. Here we report the cultivation ofLenisia limosa, gen. et sp. nov., a newly discovered breviate colonized by relatives of animal-associatedArcobacter. Physiological experiments show that the association ofL. limosawithArcobacteris driven by the transfer of hydrogen and is mutualistic, providing benefits to both partners. With whole-genome sequencing and differential proteomics, we show that an experimentally observed fitness gain ofL. limosacould be explained by the activity of a so far unknown type of NAD(P)H-accepting hydrogenase, which is expressed in the presence, but not in the absence, ofArcobacter. Differential proteomics further reveal that the presence ofLenisiastimulates expression of known ‘virulence’ factors byArcobacter. These proteins typically enable colonization of animal cells during infection5, but may in the present case act for mutual benefit. Finally, re-investigation of two currently available transcriptomic data sets of other Breviatea4reveals the presence and activity of related hydrogen-consumingArcobacter, indicating that mutualistic interaction between these two groups of microbes might be pervasive. Our results support the notion that molecular mechanisms involved in virulence can also support mutualism6, as shown here forArcobacterand Breviatea.