Nitrogen is an essential element for life. Specifically, fixed nitrogen (i.e. NH3, NH4+, NOx or N that is chemically bound to either inorganic or organic molecules and can be released by hydrolysis to form NH3 or NH4+) is useful to living organisms. Nitrogen on present-day Mars has been analysed only in the atmosphere. The inventory is a small fraction of the amount of nitrogen presumed to have been received by the planet during its accretion. Where is the missing nitrogen? Answering this question is crucial for understanding the probability of the origin and evolution of life on Mars, and for its future astrobiological exploration. The two main processes that could have removed nitrogen from the atmosphere include: (1) non-thermal escape of N atoms to space and (2) burial within the regolith as nitrates and ammonium salts. Nitrate would probably be stable in the highly oxidized surface soil of Mars and could have served as an NO3− sink. Such accumulations are observed in certain desert environments on Earth. Some NH4+ nitrogen may also be fixed and stabilized in the soil by inclusion as a structural cation in the crystal lattices of certain phyllosilicates replacing K+. Analysis of the Martian soil for traces of NO3− and NH4+ during future missions will provide important information regarding the nitrogen abundance on Mars. We hypothesize that Mars soil, as typical of extremely dry desert soils on Earth, is likely to contain at least some of the missing nitrogen as nitrate salts and some fixed ammonium bound to aluminosilicate minerals.