<p>The biological significance of the transition metal molybdenum (Mo) lies in its function at the catalytic center of several enzymes that drive a wide spectrum of redox reactions underlying global biogeochemical cycles, yet a paradox persists. While modern life ubiquitously relies on Mo, geochemical evidence suggests that its availability in early Earth’s anoxic oceans was extremely limited. Modern organisms can use Mo down to trace levels; however, the rates of Mo-dependent metabolisms slow down when Mo availability decreases, posing fundamental questions about the extent to which changing Mo abundances shaped the evolution of molybdoenzymes, and when early life began harnessing Mo. Here, we confront this evolutionary enigma by reconstructing the temporal and ecological emergence of molybdoenzymes, their transport systems, and biosynthetic pathways. In parallel, we examine biological tungsten (W) usage due to shared chemical properties and cofactor biosynthetic pathways with Mo. We provide molecular dating evidence of Mo/W utilization back to the Eo- to Mesoarchean (~3.7–3.1 Ga). These findings challenge prevailing assumptions about trace metal availability on the early Earth and underscore the profound antiquity and adaptability of Mo-based biochemistry in shaping early microbial evolution.</p>