Designing refractory high-entropy alloys (RHEAs) for high-temperature (HT) applications is an outstanding challenge given the vast possible composition space, which contains billions of candidates, and the need to optimize across multiple objectives. Here, we present an approach that accelerates the discovery of RHEA compositions with superior strength and ductility by integrating machine learning (ML), genetic search, cluster analysis, and experimental design. We iteratively synthesize and characterize 24 predicted compositions after six feedback loops. Four compositions show outstanding combinations of HT yield strength and room-temperature (RT) ductility spanning the ranges of 714–1061 MPa and 17.2%–50.0% fracture strain, respectively. We identify an attractive alloy system, ZrNbMoHfTa, particularly the composition Zr_0.13Nb_0.27Mo_0.26Hf_0.13Ta_0.21, which demonstrates a yield approaching 940 MPa at 1200 °C and favorable RT ductility with 17.2% fracture strain. The high yield strength at 1200 °C exceeds that reported for RHEAs, with 1200 °C exceeding the service temperature limit for nickel (Ni)-based superalloys. Our ML-based approach makes it possible to rapidly optimize multiple properties for materials design, thus overcoming the common problems of limited data and a vast composition space in complex materials systems while satisfying multiple objectives.