A pseudo-ternary combinatorial approach to AlxTayVzCr20Mo20Nb20Ti20Zr10 revealed the composition of refractory high-entropy alloys characterized by outstanding high-temperature yield strength. Compression testing of Al10Cr20Mo20Nb20Ti20Zr10 disclosed yield strengths of 1206 MPa at 1000 degrees C, one of the highest values reported for refractory high-entropy alloys. Ta-containing AlxTayVzCr20Mo20Nb20Ti20Zr10 presented a lower high-temperature strength, while characterization of Al10Cr20Mo20Nb20Ti20Zr10 showed C14 Al2Zr- and NbCr2-type hexagonal Laves intermetallics, with a hardness of similar to 10.5 GPa (higher than that of the body centered cubic phase, at similar to 9 GPa). The stronger bonds between Al and transition metals appear to give rise to extraordinary load-bearing capabilities in Al10Cr20Mo20Nb20Ti20Zr10, at high temperatures. Owing to this rare combination of relatively low density (6.96 g/cm(3)) and remarkable high-temperature strength, Al10Cr20Mo20Nb20Ti20Zr10 has emerged as a potential material for high-temperature structural applications.