Sleep loss is a severe problem in night-shift workers. It causes fatigue and a decrease in awareness that may be counter-acted by exercise. This randomized controlled study of 22 university students investigated the effects of exercise to prevent loss of cognitive and physical performance following sleep deprivation. We compared a single bout of 20 min circuit training to control in an experimental setting of overnight sleep loss. Outcomes included memory, cognitive tasks, and physical parameters. The occurrence of false memories was considered the main outcome. Exercise did not exert significant effects on false memories (p = 0.456). We could detect a trend to significance (p < 0.01) assessing cognitive dimensions, i.e., selective and sustained attention, and visual scanning speed. This revealed strong effects of exercise on attention (p = 0.091; Cohen’s d = 0.76; ∆14%), cognitive performance, performance speed, and perceived sleepiness (p = 0.008; d = 0.60; ∆2.4 cm VAS). This study failed to show the effects of exercise on memory function. Still, the observed effects on attention and consciousness could be considered clinically relevant, as these results encourage further research to determine its practicability and meaningfulness among night-shift workers.