Life arose in a world without oxygen and the first organisms were anaerobes. Here we investigate the gene repertoire of the prokaryote common ancestor, estimating which genes it contained and to which lineages of modern prokaryotes it was most similar in terms of gene content. Using a phylogenetic approach we found that among trees for all 8779 protein families shared between 134 archaea and 1847 bacterial genomes, only 1045 have sequences from at least two bacterial and two archaeal groups and retain the ancestral archaeal-bacterial split. Among those, the genes shared by anaerobes were identified as candidate genes for the prokaryote common ancestor, which lived in anaerobic environments. We find that these anaerobic prokaryote common ancestor genes are today most frequently distributed among methanogens and clostridia, strict anaerobes that live from low free energy changes near the thermodynamic limit of life. The anaerobic families encompass genes for bifunctional acetyl-CoA-synthase/CO-dehydrogenase, heterodisulfide reductase subunits C and A, ferredoxins, and several subunits of the Mrp-antiporter/hydrogenase family, in addition to numerous S-adenosyl methionine (SAM) dependent methyltransferases. The data indicate a major role for methyl groups in the metabolism of the prokaryote common ancestor. The data furthermore indicate that the prokaryote ancestor possessed a rotor stator ATP synthase, but lacked cytochromes and quinones as well as identifiable redox-dependent ion pumping complexes. The prokaryote ancestor did possess, however, an Mrp-type H(+)/Na(+) antiporter complex, capable of transducing geochemical pH gradients into biologically more stable Na(+)-gradients. The findings implicate a hydrothermal, autotrophic, and methyl-dependent origin of life. This article is part of a Special Issue entitled 'EBEC 2016: 19th European Bioenergetics Conference, Riva del Garda, Italy, July 2-6, 2016', edited by Prof. Paolo Bernardi.