Nitrogen is an essential element to life and exerts a strong control on global biological productivity. The rise and spread of nitrogen‐utilizing microbial metabolisms profoundly shaped the biosphere on the early Earth. Here, we reconciled gene and species trees to identify birth and horizontal gene transfer events for key nitrogen‐cycling genes, dated with a time‐calibrated tree of life, in order to examine the timing of the proliferation of these metabolisms across the tree of life. Our results provide new insights into the evolution of the early nitrogen cycle that expand on geochemical reconstructions. We observed widespread horizontal gene transfer of molybdenum‐based nitrogenase back to the Archean, minor horizontal transfer of genes for nitrate reduction in the Archean, and an increase in the proliferation of genes metabolizing nitrite around the time of the Mesoproterozoic (~1.5 Ga). The latter coincides with recent geochemical evidence for a mid‐Proterozoic rise in oxygen levels. Geochemical evidence of biological nitrate utilization in the Archean and early Proterozoic may reflect at least some contribution of dissimilatory nitrate reduction to ammonium (DNRA) rather than pure denitrification to N₂. Our results thus help unravel the relative dominance of two metabolic pathways that are not distinguishable with current geochemical tools. Overall, our findings thus provide novel constraints for understanding the evolution of the nitrogen cycle over time and provide insights into the bioavailability of various nitrogen sources in the early Earth with possible implications for the emergence of eukaryotic life.