Molybdenum dinitride (MoN2) was recently synthesized at a moderate pressure of 3.5 GPa, and a layered MoS2-type structure has been proposed. However, our first-principles calculations of thermodynamic, mechanical and dynamical properties suggest that this layered R3m structure is unstable. Therefore, stable structures of MoN2 at pressures from atmospheric pressure to 100 GPa have been further examined by utilizing a widely adopted evolutionary methodology USPEX for crystal structure prediction. We find that the ground state of the MoN2 system is a pernitride structure with space group P63/mmc which transforms to a P4/mbm phase above 82 GPa. Chemical bonding analysis shows that one could assign MoN2 as Mo4+(N24-); i.e.; Mo is formally a d2 metal, in agreement with the experimental results of Wang et al. The presence of covalent N2 dumbbells and strong bonding between Mo4+ and N24- is the source of the superior mechanical properties of these predicted ultra-incompressible MoN2 pernitrides.