Objectives: Aerobic exercise influence cognition in elderly, children, and neuropsychiatric populations. Less is known about the influence of aerobic exercise in healthy samples (particularly working age), and of different fitness levels on cognition. Two hypotheses were posed: (1) low fitness levels, compared to moderate and high, will be related to poorer cognitive performance, and (2) breakpoints for the beneficial relationship between VO₂ and cognition will be observed within the moderate-to-high fitness span. Design and Methods: The sample consisted of n=362 office workers. A submaximal cycle ergometer test estimated maximal oxygen consumption (VO_2max, mL·kg^-1·min^-1). Based on estimated VO_2max participants were split into tertiles; low (n = 121), moderate (n = 119), and high (n = 122). A cognitive test battery (9 tests), assessed processing speed, working memory, executive functions and episodic memory. Results: Both hypotheses were confirmed. Groups of moderate (≈40) and high (≈49) fitness outperformed the group of low (≈31) fitness for inhibition and episodic recognition, whereas no significant differences between moderate and high fitness were observed (ANCOVAs). Breakpoints between benefits fromVO_2max for inhibition and recognition were estimated to ≈44/43 mL·kg^-1·min^-1 (multivariate broken line regressions). Conclusions: Results suggest that it is conceivable to expect a beneficial relationship between VO_2max and some cognitive domains up to a certain fitness level. In a sample of healthy office workers, this level was estimated to 44 mL·kg^-1·min^-1. This has implications on organizational and societal levels; where incentives to improve fitness levels from low to moderate could yield desirable cognitive and health benefits in adults.