Energy efficiency is motivating the search for new high-temperature metals. Some new body-centered-cubic random multicomponent "high entropy alloys (HEAs)" based on refractory elements (Cr-Mo-Nb-Ta-V-W-Hf-Ti-Zr) possess exceptional strengths at high temperatures but the physical origins of this outstanding behavior are not known. Here, by using a recent mechanistic theory, we have computed the high-temperature (T=1300K) yield strength based on solute strengthening of over 10 million alloys within the whole Al-Cr-Mo-Nb-Ta-V-W-Hf-Ti-Zr alloy family. Also the yield strength/density has been computed. This database enables the efficient search of new alloys with exceptional high-temperature strength.