Tungsten–nitrogen (W–N) compounds are studied via a combination of first-principles calculations and variable-composition evolutionary structure searches. New candidate ground states and high-pressure phases at 3 : 2, 1 : 1, and 5 : 6 compositions are uncovered and established for possible synthesis. We found that the structures in 4/5-fold N coordination (i.e., NbO–WN and W₅N₆) are more favoured for the W–N system at low-pressures compared with the conventional 6-fold phases (rs-WN and δ-WN). We attribute the low N coordination feature of W–N ground states to the enhanced W 5d–N 2p orbital hybridization and strong covalent W–N bonding, which involves the full-filling of W–N bonding and antibonding states and can remarkably improve the mechanical strength and hardness. These findings not only clarify the phase diagram of the W–N system, but also shed light on the correlations of hardness with microscopic crystal and electronic structures.