Aircraft pilots face a high mental workload (MW) under environmental constraints induced by high altitude and sometimes sleep restriction (SR). Our aim was to assess the combined effects of hypoxia and sleep restriction on cognitive and physiological responses to different MW levels using the Multi-Attribute Test Battery (MATB)-II with an additional auditory Oddball-like task. Seventeen healthy subjects were subjected in random order to three 12-min periods of increased MW level (low, medium, and high): sleep restriction (SR, 6 h TST), hypoxia (HY, 2 h, F_IO₂ = 13.6%, ~3500 m vs. normoxia, NO, F_IO₂ = 21%). Following each MW level, participants completed the NASA-TLX subjective MW scale. Increasing MW decreases performance on the MATB-II Tracking task (p = 0.001, MW difficulty main effect) and increases NASA-TLX (p = 0.001). In the combined HY/SR condition, MATB-II performance was lower, and the NASA-TLX score was higher compared with the NO/HS condition, while no effect of hypoxia alone was observed. In the accuracy of the auditory task, there is a significant interaction between hypoxia and MW difficulty (F_(2–176) = 3.14, p = 0.04), with lower values at high MW under hypoxic conditions. Breathing rate, pupil size, and amplitude of pupil dilation response (PDR) to auditory stimuli are associated with increased MW. These parameters are the best predictors of increased MW, independently of physiological constraints. Adding ECG, SpO₂, or electrodermal conductance does not improve model performance. In conclusion, hypoxia and sleep restriction have an additive effect on MW. Physiological and electrophysiological responses must be taken into account when designing a MW predictive model and cross-validation.