The aim of this cross-sectional study was to evaluate the relationships between cognitively engaging exercise (i.e., game-based and coordination exercises), executive functions (i.e., inhibitory control and working memory), and physical fitness. Forty junior tennis players (6–12 years old), who regularly participated in tennis lessons (2.55 years, SD = 1.61) prior to the study, were investigated. All participants completed evaluations of executive functions (inhibitory control and working memory) at rest. The duration of each lessons’ instructional activities, including coordination training, game-based exercise, rallying, and non-physical activity (explanations and breaks), was recorded. Physical fitness was evaluated using the Tennis Field Test. A longer duration of game-based exercise was positively correlated with inhibitory control and physical fitness. Coordination training was associated with improved working memory. Non-physical activity was inversely correlated with inhibitory control, working memory, and physical fitness. The results suggest that game-based tennis lessons have beneficial effects on inhibitory control and physical fitness levels, and a longer duration of coordination training is associated with better working memory. The present study indicates that shortened non-physical activity time within a sports setting is associated with the development of executive functions and physical fitness.