Refractory high-entropy alloys (RHEAs) have promising applications as the new generation of high-temperature alloys in hypersonic vehicles, aero-engines, gas turbines, and nuclear power plants. This study focuses on the microstructures and mechanical properties of the NbMoTaW(HfN)_x (x = 0, 0.3, 0.7, and 1.0) RHEAs. The alloys consist of multiple phases of body-centered cubic (BCC), hafnium nitride (HfN), or multicomponent nitride (MN) phases. As the x contents increase, the grain size becomes smaller, and the strength gradually increases. The compressive yield strengths of the NbMoTaWHfN RHEA at ambient temperature, 1000, 1400, and 1800 °C were found to be 1682, 1192, 792, and 288 MPa, respectively. The high-temperature strength of this alloy is an inspiring result that exceeds the high temperature and strength of most known alloys, including high-entropy alloys, refractory metals, and superalloys. The HfN phase has a significant effect on strengthening due to its high structural stability and sluggish grain coarsening, even at ultra-high temperatures. Its superior properties endow the NbMoTaWHfN RHEA with potential for a wide range of engineering applications at ultra-high temperatures. This work offers a strategy for the design of high-temperature alloys and proposes an ultra-high-temperature alloy with potential for future engineering applications.