Refractory high entropy alloy (RHEAs) are widely regarded as promising replacements for the state-of-the-art Ni-based superalloys in ultrahigh-temperature (UHT) applications. As a new type of high-temperature (HT) materials, RHEAs are also facing the “old challenge” in solving the trade-off between ductility, mainly at room temperature (RT), and strength, at both HT and RT [1]. While the solid solution hardening strategy can be applied to improve the HT strength, solid solution softening by either substitutional or interstitial alloying, which is a well-documented phenomenon existing mainly in bcc-structured materials [2], can be utilized to soften the originally brittle alloys in order to achieve some tensile ductility (even marginal) at RT. Here, the effect of minor additions of substitutional elements Al, Cu, Fe and Mn on the RT and elevated-temperature hardness of a single bcc phase Hf₂₀Nb₃₁Ta₃₁Ti₁₈ RHEA was studied. Interestingly, 2.5 at. % addition of Fe hardened the base Hf₂₀Nb₃₁Ta₃₁Ti₁₈ alloy in the temperature range from RT to 800 ^oC, while the same amount addition of Al, Cu and Mn softened the base alloy from RT to 1000 ^oC. The combination of the solid solution softening effect at RT and the solid solution hardening effect at HT provides a new research direction to develop novel RHEAs simultaneously possessing RT tensile ductility and decent HT strength.