Nitrogen’s isotopic ratio was the first indicator of substantial atmospheric evolution on Mars and its value has been recently measured with high precision. Photochemical escape and sputtering would have caused much more fractionation in the atmosphere than observed, and previous models proposed a massive early CO2 atmosphere or large recent volcanic outgassing as mitigations. A common feature of these models is that the atmospheric nitrogen has been in a steady state - the escape rate balances the outgassing rate - from 1 to more than 3 billion years ago. Here we show that a previously unknown family of evolutionary tracks can explain the size and the isotopic composition of the atmospheric nitrogen. In this family of “dynamical” solutions, the nitrogen has never been in a steady state, and its partial pressure gradually descends to the present-day value over the past 4 billion years. The dynamical solutions do not require a massive early CO2 atmosphere and are fully consistent with small recent volcanic outgassing indicated by both geologic mapping and the atmospheric 36Ar/38Ar ratio. The history of atmospheric nitrogen on Mars is thus likely characterized by the dynamical solutions, in which the initial partial pressure of nitrogen bears upon the current pressure and isotopic composition. Our Monte Carlo simulations indicate that the pressure of N2 at 3.8 billion years ago was 20–400 mbar, with 250 mbar being the median value and the spread mostly due to the uncertainty in the sputtering loss rate. Nitrogen thus likely contributed substantially to the warming and the formation of sustained surface melting on early Mars.