High-entropy alloys (HEAs) manufactured with refractory elements are candidates for high-temperature structural applications. To enhance our understanding of oxidation in these complex systems, the early stages of oxidation on the surface of Al₁₀Nb₁₅Ta₅Ti₃₀Zr₄₀ were studied using density functional theory and thermodynamic modeling. Surface slabs were generated from bulk configurations sampled from equilibrium using a multicell Monte Carlo method for phase prediction. The bulk structure was found to be a single BCC phase in good agreement with experimental observations. The oxygen adsorbed with a strong preference for sites with Ti and Zr and avoided sites with Nb–Al and Nb–Ta. The surface was shown to be highly reactive to oxygen, yielding a dominating oxygen coverage of two monolayers over the temperature range of 100 to 2600 K and an oxygen pressure range of 10^–30 to 10⁵ bar. Recovering a clean surface slab was not achieved until pressures approached vacuum conditions and temperature exceeded 1900 K, demonstrating the difficulty of oxygen removal from the surface. Grand canonical Monte Carlo simulations showed that high Nb content in the top surface layer reduced the surface reactivity to incoming oxygen. Inward oxygen diffusion at low coverage was preferred in regions rich with Zr but slowed with the addition of Ti and Al. Diffusion rates drastically decreased at 1 ML, especially in the region rich with Ti and Zr, where strong metal–oxygen bonds were reported. Our results indicated that a high content of Ti and Zr increased the reactivity of the HEA surface to oxygen. The presence of Nb also enhanced the resistance to oxygen adsorption, especially when partnered with Al and Ta. Inward oxygen diffusion was likely to occur at low coverage in regions rich with Zr but could be protected against with the addition of Al and Ti. The limitations of the present work are discussed. This study may provide insights that assist with devising short- and long-term mitigation strategies against material degradation related to high-temperature oxidation.