Refractory High Entropy Alloys (RHEA) are considered novel promising high temperature materials for structural applications at ultra-high temperatures primarily due to their attractive mechanical properties. By contrast, the oxidation behavior of RHEA has raised concern owing to pest oxidation, significant weight changes, scale spallation or even complete oxidation at elevated temperatures. In this contribution, results on high temperature oxidation behavior of RHEA within the alloy system Ta-Mo-Cr-Ti-Al as well as selected results of relevant studies avaliable in the literature will be presented. It will be shown that while many RHEA indeed suffer from poor oxidation resistance, some RHEA, e.g. the equiatomic Ta-Mo-Cr-Ti-Al alloy, exhibit very good protectiveness which is attributed to the formation of rarely encountered Ta-Cr-based complex oxides. Thermodynamic and kinetic aspects of oxide formation and growth will be discussed to understand the oxidation mechanisms.