Motivated by exploring new high temperature ceramics which have excellent mechanical properties, we systematically search for all the stable compounds and their crystal structures in the binary Hf-N system by combining the evolutionary algorithm with first principle calculation. In addition to the well-known rock-salt HfN, we find five other novel compounds, i.e., Hf6N(R-3), Hf3N(P6322), Hf3N2(R-3m), Hf5N6(C2/m), and Hf3N4(C2/m). Then, their phonon frequencies are calculated so that the dynamical stabilities are known. Their high temperature thermodynamic stabilities are further confirmed and the Gibbs free energies are calculated in thequasi-harmonic approximation. All of these structures are thermodynamic stable when the temperature is lower than 1500 K. However, as temperature increases, the structuresHf5N6(C2/m) and Hf3N4(C2/m) become meta-stable. Meanwhile, some meta-stable structures, including Hf2N (P42/mnm), Hf4N3 (C2/m), Hf6N5(C2/m), Hf4N5(I4/m), Hf3N4 (I-43d), and Hf3N4 (Pnma), each of which has higher symmetry and lower formation enthalpy, are all listed. At the same time, our results of Hf3N4 testify that C2/m structure is stabler than Pnma and I-43d structures when the temperature is lower than 2000 K, which is different from the conclusion given by Bazhanov []. The results also show that the difference in Gibbs free energy between C2/m and Pnma Hf3N4 structure decreases with temperature increasing. Thus, we speculate that the C2/m Hf3N4 transforms into Pnma Hf3N4 when the temperature is above 2000 K. The mechanical properties, including the elastic constant, bulk modulus, shear modulus, Young's modulus and hardness, are systematically investigated. The hardness first increases, reaching a maximum at Hf5N6 (21 GPa), and then decreases with increasing nitrogen content. Besides, Hf3N2 and Hf4N5 both exhibit relatively high hardness value of 19 GPa, while the hardness of HfN is 15 GPa. Finally, the electron densities of states and crystal orbital Hamilton populations are calculated so that the mechanic origins can be analyzed from the electronic structures of these phases. The crystal orbital Hamilton populations show that the strength of Hf-N covalent bonding increases with increasing nitrogen content, however, it has an exceptional peak for Hf3N2, which can be used to explain the relatively high hardness of this structure. Beside covalent bonding strength, structural vacancy can also affect their mechanical properties. It is concluded that the strong covalent bonding and low structural vacancy both can explain the good mechanical performance of Hf5N6.