Metallic alloys containing multiple principal alloying elements have created a growing interest in exploring the property limits of metals and understanding the underlying physical mechanisms. Refractory high-entropy alloys have drawn particular attention due to their high melting points and excellent softening resistance, which are the two key requirements for high-temperature applications. Their compositional space is immense even after considering cost and recyclability restrictions, providing abundant design opportunities. However, refractory high-entropy alloys often exhibit apparent brittleness and oxidation susceptibility, which remain important challenges for their processing and application. Here, utilizing natural-mixing characteristics among refractory elements, we designed a Ti38V15Nb23Hf24 refractory high-entropy alloy that exhibits >20% tensile ductility in the as-cast state, and physicochemical stability at high temperatures. Exploring the underlying deformation mechanisms across multiple length scales, we observe that a rare β′-phase plays an intriguing role in the mechanical response of this alloy. These results reveal the effectiveness of natural-mixing tendencies in expediting high-entropy alloy discovery.