Objectives: The primary goals of this study were to determine the effects of a physical activity intervention on the set-shifting aspect of executive function and to explore the potential mechanistic role of cardiac autonomic control, as assessed by heart rate variability (HRV), in the relationship between physical activity and executive function in obese young adolescents. Method: Obese young adolescents were randomized either to participate in a physical activity program (n = 25) or to serve as the wait-list control (n = 25) for a 3-month intervention. Outcome measures included physical fitness, obesity status, executive function, and HRV; these measures were assessed at baseline and within 1 week of the conclusion of the intervention. Results: The physical activity program improved the participants’ physical fitness and obesity status. The program also improved executive function–related set-shifting performance, as measured by the total number of errors, and increased the HRV indices of normalized low frequency (nLF) and normalized high frequency (nHF). A positive correlation between the nHF time changes and the total number of errors was also observed. Conclusion: These findings suggest that 3 months of a physical activity intervention effectively increase physical fitness and improve the set-shifting aspect of executive function in obese young adolescents. Furthermore, the physical activity–related alterations in cardiac autonomic control, particularly the parasympathetic response, may be associated with enhanced executive function.