<p>Refractory high-entropy alloys (RHEAs) are of prime interest for their potential use as high-temperature materials in next-generation gas turbine engines. Improving the strength-plasticity trade-off has been a grand challenge for RHEAs due to the vast composition search space and non-availability of reliable models. In this paper, we have developed a machine learning-based plasticity model and yield strength model in order to define criteria for the yield strength-plasticity trade-off. A robust probabilistic-based uncertainty quantification is performed to identify confidence in predictions. Model descriptors are also analyzed through a state-of-the-art model explainability technique. Our analysis not only is consistent with known physics, but also provides new insights for identifying critical descriptors dictating the strength-plasticity trade-off. This can be used as a guideline to discover new compositions with desired properties. Finally, model predictions are validated through processing and characterization of two new RHEA compositions.</p>