Introduction Feelings of fatigue are reduced after a session of continuous exercise of low-to-moderate intensity lasting 20 min or more, but only when feelings of energy are increased. Feelings of fatigue and energy have not been described after fatiguing, high-intensity interval exercise. Cerebral oxygenation has been implicated as a central correlate of fatigability, but it has not been studied concurrent with perceived fatigue during or after exercise. Methods Fifteen recreationally active participants (8 women, 7 men) completed bouts of sprint interval cycling (four, 30-s all-out sprints each followed by 4 min of active recovery) and a time- and work-matched bout of constant resistance cycling. Oxygenation (oxygenated hemoglobin [HbO2]) and deoxygenation (deoxygenated hemoglobin [HHb]) in the dorsolateral prefrontal cortex were measured using near-infrared spectroscopy. Fatigue ratings during each sprint and feelings of fatigue and energy during recovery were assessed. Results Increases in HbO2 and HHb in frontal cortex were greater during sprint cycling than during constant resistance cycling (P = 0.001). Fatigability (decreased power output) increased over successive sprints (P = 0.001). About 95% of the increase in fatigue ratings across sprints (P < 0.001) was accounted for by fatigability and cortical HbO2. Feelings of fatigue were decreased (P < 0.001) and feelings of energy were increased (P < 0.05) across sprint recovery periods but were unchanged during constant resistance cycling. About 85% of the changes in feelings of fatigue or energy during recovery were explained by fatigue ratings across sprints and maximum HbO2 in the cortex during recovery. Conclusion Repeated, high-intensity sprints were fatiguing, but paradoxical reductions in feelings of fatigue and increases in feelings of energy occurred during recovery that were accounted for by ratings of fatigue during exercise and oxygenation in the dorsolateral prefrontal cortex during recovery.