The evolution of nitrogen fixation undoubtedly altered nearly all corners of the biosphere, given the essential role of nitrogen in the synthesis of biomass. To date, there is no unified view on what planetary conditions gave rise to nitrogen fixation or how these conditions have sustained it evolutionarily. Intriguingly, the concentrations of metals that nitrogenases require to function have changed throughout Earth's history. In this review, we describe the interconnection of the metal and nitrogen cycles with nitrogenase evolution and the importance of ancient ecology in the formation of the modern nitrogen cycle. We argue that exploration of the nitrogen cycle's deep past will provide insights into humanity's immediate environmental challenges centered on nitrogen availability.