Here the discovery of refractory multi-principal element alloys (MPEAs) with high-temperature strength and stability is pursued within a constrained and application-relevant design space. A comprehensive approach is developed and applied to explore all 165 ternary systems in the Al-Ce-Fe-Hf-Mo-Nb-Ta-Ti-V-W-Zr family. A subset of ternary systems that contain large areas in composition–temperature space with high strength and robust BCC phase stability is found. Twelve sets of high-performing alloys are identified, each set optimized for one combination of phase constraint, optimization target, and temperature range. Preliminary mechanical tests support the viability of the method. This work highlights the importance of considering phase stability, exploring non-equiatomic regions of composition space, and applying application-relevant constraints. Parts I and II provide three down-selection techniques for identifying high-performing BCC refractory MPEAs, design guidelines, and many candidates predicted to have BCC phase stability and strengths 2–3 times higher than any reported to date.