The present study examined the effects of a 9-month randomized control physical activity intervention aimed at improving cardiorespiratory fitness on changes in working memory performance in preadolescent children relative to a waitlist control group. Participants performed a modified Sternberg task, which manipulated working memory demands based on encoding set sizes, while task performance and the contingent negative variation (CNV) event-related brain potential were measured. Analyses revealed that the physical activity intervention led to increases in cardiorespiratory fitness and improved Sternberg task performance. Further, the beneficial effects of the physical activity intervention were greater for a task condition requiring greater working memory demands. In addition, the intervention group exhibited larger initial CNV at the frontal electrode site, relative to the waitlist group at post-test; an effect not observed during the pre-test. These results indicate that increases in cardiorespiratory fitness are associated with improvements in the cognitive control of working memory in preadolescent children.