Refractory high-entropy alloys (RHEAs) are a promising class of alloys that show elevated-temperature yield strengths and have potential to use as high-performance materials in gas turbine engines. However, exploring the vast RHEA compositional space experimentally is challenging, and only a small fraction of this space has been explored to date. This work demonstrates the development of a state-of-the-art machine learning (ML) predictive framework coupled with optimization methods to intelligently explore the vast compositional space and drive the search in a direction that improves high-temperature yield strengths. Our forward yield strength model is shown to have a significantly improved predictive accuracy relative to the state-of-the-art approach, and also provides inherent uncertainty quantification through the use of repeated k-fold cross-validation. Upon developing and validating a robust yield strength prediction model, the coupled framework is used to discover new RHEAs with superior high temperature yield strength. We have shown that RHEA compositions can be customized to have maximum yield strength at a specific temperature.