Introduction Both sleep deprivation and hypoxia have been shown to impair executive function. Conversely, moderate intensity exercise is known to improve executive function. In a multi-experiment study, we tested the hypotheses that moderate intensity exercise would ameliorate any decline in executive function after i) three consecutive nights of partial sleep deprivation (PSD) (Experiment 1) and ii) the isolated and combined effects of a single night of total sleep deprivation (TSD) and acute hypoxia (Experiment 2). Methods Using a rigorous randomised controlled crossover design, 12 healthy participants volunteered in each experiment (24 total, 5 females). In both experiments seven executive function tasks (2-choice reaction time, logical relations, manikin, mathematical processing, 1-back, 2-back, 3-back) were completed at rest and during 20 min semi-recumbent, moderate intensity cycling. Tasks were completed in the following conditions: before and after three consecutive nights of PSD and habitual sleep (Experiment 1) and in normoxia and acute hypoxia (FIO2 = 0.12) following one night of habitual sleep and one night of TSD (Experiment 2). Results Although the effects of three nights of PSD on executive functions were inconsistent, one night of TSD (regardless of hypoxic status) reduced executive functions. Significantly, regardless of sleep or hypoxic status, executive functions are improved during an acute bout of moderate intensity exercise. Conclusion These novel data indicate that moderate intensity exercise improves executive function performance after both PSD and TSD, regardless of hypoxic status. The key determinants and/or mechanism(s) responsible for this improvement still need to be elucidated. Future work should seek to identify these mechanisms and translate these significant findings into occupational and skilled performance settings.