Since the discovery of superconductivity in boron-doped diamond with a critical temperature (TC) near 4 K, great interest has been attracted in hard superconductors such as transition-metal nitrides and carbides. Here we report the new discovery of superconductivity in polycrystalline hexagonal ε-NbN synthesized at high pressure and high temperature. Direct magnetization and electrical resistivity measurements demonstrate that the superconductivity in bulk polycrystalline hexagonal ε-NbN is below ∼11.6 K, which is significantly higher than that for boron-doped diamond. The nature of superconductivity in hexagonal ε-NbN and the physical mechanism for the relatively lower TC have been addressed by the weaker bonding in the Nb-N network, the co-planarity of Nb-N layer as well as its relatively weaker electron-phonon coupling, as compared with the cubic δ-NbN counterpart. Moreover, the newly discovered ε-NbN superconductor remains stable at pressures up to ∼20 GPa and is significantly harder than cubic δ-NbN; it is as hard as sapphire, ultra-incompressible and has a high shear rigidity of 201 GPa to rival hard/superhard material γ-B (∼227 GPa). This exploration opens a new class of highly desirable materials combining the outstanding mechanical/elastic properties with superconductivity, which may be particularly attractive for its technological and engineering applications in extreme environments.