Nb-based refractory alloys are among those available materials for ultrahigh-temperature applications, while the trade-off between mechanical properties and oxidation resistance is a long-standing scientific challenge. Two commercial Nb alloys, C103 (Nb92.5Hf5.5Ti2, at.%) and WC3009 (Nb74.5Hf20W5.5, at.%), both with good room-temperature ductility but with various high-temperature strength, were modified here in this work with the intention to simultaneously achieve high strength at high temperatures, reasonable ductility at room temperature, and decent oxidation resistance. Particularly, the contents of alloying elements Hf, W and Ti were varied with reference to C103 and WC3009, considering Hf is good for strength and not detrimental to room-temperature ductility, W is particularly useful for the high-temperature strength, and Ti helps to improve oxidation resistance. The mechanical properties of these modified Nb-based refractory alloys were measured at room temperature and 1200 °C, and their oxidation resistance at 800 °C, 1000 °C and 1200 °C was also evaluated. Among the newly developed Nb-based refractory alloys, Nb68.5Hf15Ti10W6.5 (10Ti) and Nb55.5Hf20Ti15W9.5 (15Ti) showed much improved oxidation resistance compared to C103 and WC3009, at a relatively small cost of reduced high-temperature strength compared to WC3009. The alloying effect of Hf, W and Ti on the mechanical properties at both room-temperature and high-temperatures, the oxidation resistance, and more importantly their balance was discussed, providing important insights into the further development of Nb-based refractory alloys targeting ultrahigh-temperature applications.