Oxidoreductases mediate electron transfer (i.e., redox) reactions across the tree of life and ultimately facilitate the biologically driven fluxes of hydrogen, carbon, nitrogen, oxygen, and sulfur on Earth. The core enzymes responsible for these reactions are ancient, often small in size, and highly diverse in amino acid sequence, and many require specific transition metals in their active sites. Here we reconstruct the evolution of metal-binding domains in extant oxidoreductases using a flexible network approach and permissive profile alignments based on available microbial genome data. Our results suggest there were at least 10 independent origins of redox domain families. However, we also identified multiple ancient connections between Fe2S2- (adrenodoxin-like) and heme- (cytochrome c) binding domains. Our results suggest that these two iron-containing redox families had a single common ancestor that underwent duplication and divergence. The iron-containing protein family constitutes ∼50% of all metal-containing oxidoreductases and potentially catalyzed redox reactions in the Archean oceans. Heme-binding domains seem to be derived via modular evolutionary processes that ultimately form the backbone of redox reactions in both anaerobic and aerobic respiration and photosynthesis. The empirically discovered network allows us to peer into the ancient history of microbial metabolism on our planet.