Molybdenum (Mo) is an essential nutrient for most living organisms, serving as a cofactor in a diverse array of molybdoenzymes that catalyze key reactions in several elemental cycles. However, geochemical data suggest that dissolved Mo concentrations in the Archean ocean (before 2.5 billion years ago) were 1 to 2 orders of magnitude lower than today, raising questions about its bioavailability to early life. Here, we apply a phylogenomic approach to chart the modern biological and environmental distribution of Mo-related enzymes and use phylogenetic reconciliations to reconstruct the evolutionary history of biological Mo usage. Our results reveal the ubiquity of molybdoenzymes across contemporary organisms inhabiting diverse environments. Furthermore, phylogenetic evidence indicates that the earliest molybdoenzymes stem back to the Paleo/Mesoarchean (3.5 to 3.0 Gya), facilitating critical energy-harnessing reactions in some of Earth s most ancient life forms. Taken together, our findings challenge the prevailing view of limited Mo bioavailability on the anoxic early Earth.