Background: As physical activity benefits brain health whereas air pollution damages it, the cognitive response to these exposures may interact. Purpose: This study aimed to assess the short-term joint effect of physical activity and air pollution on cognitive function in a panel of healthy young adults. Methods: We followed ninety healthy subjects aged around 22 years from September 2020 to June 2021 and measured their personal exposure to fine particulate matter (PM2.5) (μg/m3) and daily accelerometer-based moderate-to-vigorous physical activity (MVPA) (min/day) in 4 one-week-long sessions over the study period. At the end of each measurement session, we assessed executive function using Stroop color-word test and collected resting-state electroencephalogram (EEG) signals. Results: We found short-term PM2.5 exposure damaged executive function (βPM25 = 0.0064, p = 0.039) but physical activity could counterbalance it (βMVPA = −0.0047, p = 0.048), whereby beta-3 wave played as a potential mediating role. MVPA-induced improvement on executive function was larger in polluted air (βMVPA = −0.010, p = 0.035) than that in clean air (βMVPA = −0.003, p = 0.45). To offset the negative effect of air pollution on cognitive function, individuals should do extra 13.6 min MVPA every day for every 10 μg/m3 increase in daily PM2.5. Conclusion: This study implies that physical activity could be used as a preventive approach to compensate the cognitive damages of air pollution.