Molecular nitrogen is the most commonly assumed background gas that supports habitability on rocky planets. Despite its chemical inertness, nitrogen molecules are broken by lightning, hot volcanic vents, and bolide impacts, and can be converted into soluble nitrogen compounds and then sequestered in the ocean. The very stability of nitrogen, and that of nitrogen-based habitability, is thus called into question. Here we determine the lifetime of molecular nitrogen vis-à-vis aqueous sequestration, by developing a novel model that couples atmospheric photochemistry and oceanic chemistry. We find that HNO, the dominant nitrogen compound produced in anoxic atmospheres, is converted to N2O in the ocean, rather than oxidized to nitrites or nitrates as previously assumed. This N2O is then released back into the atmosphere and quickly converted to N2. We also find that the deposition rate of NO is severely limited by the kinetics of the aqueous-phase reaction that converts NO to nitrites in the ocean. Putting these insights together, we conclude that the atmosphere must produce nitrogen species at least as oxidized as NO2 and HNO2 to enable aqueous sequestration. The lifetime of molecular nitrogen in anoxic atmospheres is determined to be >1 billion years on temperate planets of both Sun-like and M dwarf stars. This result upholds the validity of molecular nitrogen as a universal background gas on rocky planets.