Multi-principal-element metallic alloys have created a growing interest that is unprecedented in metallurgical history, in exploring the property limits of metals and the governing physical mechanisms. Refractory high-entropy alloys (RHEAs) have drawn particular attention due to their (i) high melting points and excellent softening-resistance, which are the two key requirements for high-temperature applications; and (ii) compositional space, which is immense even after considering cost and recyclability restrictions. However, RHEAs also exhibit intrinsic brittleness and oxidation-susceptibility, which remain as significant challenges for their processing and application. Here, utilizing natural-mixing characteristics amongst refractory elements, we designed a Ti38V15Nb23Hf24 RHEA that exhibits >20% tensile ductility already at the as-cast state, and physicochemical stability at high-temperatures. Exploring the underlying deformation mechanisms across multiple length-scales, we observe that a rare beta prime precipitation strengthening mechanism governs its intriguing mechanical response. These results also reveal the effectiveness of natural-mixing tendencies in expediting HEA discovery.