High entropy alloys (HEAs), which consist of more than five major elements in near equal atomic concentration, have recently attracted a great deal of attention because of their exceptional mechanical properties and thermal stabilities. Especially, NbMoTaW refractory alloys have been reported to exhibit superior high-temperature strength, being considered for potential applications under the extreme environment at high temperatures. In this study, we suggest a new concept of refractory HEAs-based composites containing nano-scale oxides, wherein the uniformly dispersed oxides can enhance heat/oxidation resistance of HEAs further. Mechanical alloying and spark plasma sintering were employed to produce composites with uniformly dispersed oxides and nano-scale crystallines. We will discuss the relations among process conditions (e.g., ball-milling duration and sintering temperature), microstructures (e.g., degree of dispersion of oxides, crystalline size), and heat/oxidation resistance of HEAs.