Entamoeba histolytica and Spironucleus barkhanus have genes that encode short iron-dependent hydrogenases (Fe-hydrogenases), even though these protists lack hydrogenosomes. To understand better the biochemistry of the protist Fe-hydrogenases, we prepared a recombinant E. histolytica short Fe-hydrogenase and measured its activity in vitro. A Giardia lamblia gene encoding a short Fe-hydrogenase was identified from shotgun genomic sequences, and RT-PCR showed that cultured entamoebas and giardias transcribe short Fe-hydrogenase mRNAs. A second E. histolytica gene, which encoded a long Fe-hydrogenase, was identified from shotgun genomic sequences. Phylogenetic analyses suggested that the short Fe-hydrogenase genes of entamoeba and diplomonads share a common ancestor, while the long Fe-hydrogenase gene of entamoeba appears to have been laterally transferred from a bacterium. These results are discussed in the context of competing ideas for the origins of genes encoding fermentation enzymes of these protists.