Recent findings by the Mars Science Laboratory (MSL) have confirmed the presence of nitrates near Gale Crater on Mars. In this work, we consider the formation and deposition of HNOx species in cold early Mars climates. We find that solar energetic particles could facilitate nitrogen fixation by photochemically generating pernitric and nitric acid, which then deposit onto icy particles that settle onto Mars’ surface. This study demonstrates that such deposition would be more efficient under higher atmospheric pressures, consistent with Mars’ ancient atmosphere, and could account for the nitrate levels detected by the MSL. We find a more rapid deposition rate for pernitric acid over nitric acid (in agreement with Smith et al., 2014), and a significant enhancement of deposition rates through consideration of deposition onto icy particles. This distinction could be crucial for interpreting the MSL data.