Refractory metal-based multi-principal element alloys (MPEAs) with a body centered cubic (BCC) structure can maintain excellent mechanical properties at high temperatures. To exploit the enhanced mechanical properties, tailored MPEAs are needed with both strength and BCC stability sufficient for a given service requirement. However, strength and stability vary drastically with temperature, number of elements, and composition of elements. Through analytical calculations, we investigate virtually all MPEAs from the Al-Cr-Fe-Hf-Mo-Nb-Ta-Ti-V- W-Zr family with up to eleven elements to identify candidates with high yield strength or specific yield strength. These results are filtered with CALPHAD phase stability predictions to ensure sufficient BCC stability or metastability at high temperatures. We also present a method of efficient searching for novel alloys that combines (1) highly optimized Black-Box Optimization (BBO) multi-stage investigation of individual alloy systems using CALPHAD modeling and surrogate models for targeting properties with (2) on-the-fly decisions on systems to investigate and resources to allocate to each. Select compositions predicted to maintain high strength or specific strength and sufficient BCC stability are manufactured and mechanically tested to validate the tailored MPEA design process.