We fabricated Nb42Mo20Ti13Cr12V12Ta1, a novel refractory high-entropy alloy (RHEA) enriched with niobium (Nb), by following a high-energy ball milling and spark plasma sintering (SPS) method. The microstructure of the bulk RHEA formed a single body-centered cubic (BCC) matrix with in-situ-formed carbide dispersoids. The combination of the effect of the severe deformations caused by the milling, the short sintering time, and the impedance of the grain growth caused by the dispersoids led to the formation of nano-sized grains, in spite of the high sintering temperature of 1200 degrees C. This resulted in outstanding mechanical properties. The bulk Nb42Mo20Ti13Cr12V12Ta1 RHEA exhibits a compressive yield strength of 2680 MPa, a maximum strength of 3896 MPa, and a Vickers hardness of 741 HV. The excellent mechanical properties of the alloy can be attributed to the strengthening of the dispersion and the solid solution, coupled with the grain refinement effects.