Hydrogenosomes are double-membraned ATP-producing and hydrogen-producing organelles of diverse anaerobic eukaryotes. In some versions of endosymbiotic theory they are suggested to be homologues of mitochondria, but alternative views suggest they arose from an anaerobic bacterium that was distinct from the mitochondrial endosymbiont. Here we show that the 51-kDa and 24-kDa subunits of the NADH dehydrogenase module in complex I, the first step in the mitochondrial respiratory chain, are active in hydrogenosomes of Trichomonas vaginalis. Like mitochondrial NADH dehydrogenase, the purified Trichomonas enzyme can reduce a variety of electron carriers including ubiquinone, but unlike the mitochondrial enzyme it can also reduce ferredoxin, the electron carrier used for hydrogen production. The presence of NADH dehydrogenase solves the long-standing conundrum of how hydrogenosomes regenerate NAD+ after malate oxidation. Phylogenetic analyses show that the Trichomonas 51-kDa homologue shares common ancestry with the mitochondrial enzyme. Recruitment of complex I subunits into a H2-producing pathway provides evidence that mitochondria and hydrogenosomes are aerobic and anaerobic homologues of the same endosymbiotically derived organelle.