The evolution of aerobic respiration was likely linked to the origins of oxygenic Cyanobacteria. Close phylogenetic neighbors to Cyanobacteria, such as Margulisbacteria (RBX-1 and ZB3), Saganbacteria (WOR-1), Melainabacteria and Sericytochromatia, may constrain the metabolic platform in which aerobic respiration arose. Here, we analyze genomic sequences and predict that sediment-associated Margulisbacteria have a fermentation-based metabolism featuring a variety of hydrogenases, a streamlined nitrogenase, and electron bifurcating complexes involved in cycling of reducing equivalents. The genomes of ocean-associated Margulisbacteria encode an electron transport chain that may support aerobic growth. Some Saganbacteria genomes encode various hydrogenases, and others may be able to use O2 under certain conditions via a putative novel type of heme copper O2 reductase. Similarly, Melainabacteria have diverse energy metabolisms and are capable of fermentation and aerobic or anaerobic respiration. The ancestor of all these groups may have been an anaerobe in which fermentation and H2 metabolism were central metabolic features. The ability to use O2 as a terminal electron acceptor must have been subsequently acquired by these lineages.