The structures and properties of rhenium nitrides are studied with density function based first principle method. New candidate ground states or high-pressure phases at Re:N ratios of 3:2, 1:3, and 1:4 are identified via a series of evolutionary structure searches. We find that the 3D polyhedral stacking with strong covalent N-N and Re-N bonding could stabilize Re nitrides to form nitrogen rich phases, meanwhile, remarkably improve the mechanical performance than that of sub-nitrides, as Re3N, Re2N, and Re3N2. By evaluating the trends of the crystal configuration, electronic structure, elastic properties, and hardness as a function of the N concentration, we proves that the N content is the key factor affecting the metallicity and hardness of Re nitrides.