The search for new high-temperature alloys that can enable higher-efficiency/lower-emissions power generation has accelerated with the discovery of body-centered cubic (bcc) refractory High Entropy Alloys (HEAs). These many-component, non-dilute alloys in the Cr-Mo-W-V-Nb-Ta-Ti-Zr-Hf-Al family hold the potential for combining high strength and thermodynamic stability at high temperature with low density and room-temperature ductility, but searching the immense compositional space is daunting. Here, very recent theories and expanded thermodynamic tools are used to guide the discovery of new alloys satisfying the required suite of properties. We present the dataset we generated in search for such alloys, including 5-component equicomposition alloys, as well as new quinary and quarternary alloys in the Hf-Mo-Nb-Ta-Ti space having even better overall properties (high strength, high strength retention, good ductility, light weight and single phase).