Physical activity (PA) plays an important role in cognitive health. However, the underlying mechanisms are not fully understood. Cardiac autonomic balance is influenced by PA and implicated in dementia pathogenesis. We examined whether autonomic balance mediates the association between PA and cognitive function. The sample included 1939 participants from the Coronary Artery Risk Development in Young Adults study who completed cognitive testing after 30-year follow-up (baseline: mean age 25.2 ± 3.5y; 58% women; 43% Black). Moderate to vigorous intensity PA (MVPA) was obtained in 7 consecutive examinations over 20 years (Year 0-Year 20). Cardiac autonomic balance was assessed at Year 20 via resting heart rate (RHR), standard deviation normal to normal (SDNN) and root mean square of successive differences (RMSSD). We used group-based trajectory modeling to identify homogenous MVPA trajectory groups, and formal mediation analysis to test whether autonomic function indices mediate the association between MVPA trajectories and cognition. We identified three distinct PA trajectory patterns: (1) Below MVPA guidelines (n = 1122; 57.9%); (2) Meeting MVPA guidelines (n = 652; 33.6%); and (3) Exceeding MVPA guidelines (n = 165; 8.5%). Meeting and exceeding MVPA guidelines were related to better autonomic balance overall, and to improved semantic fluency performance. Statistically, the association between higher MVPA level and verbal ability was mediated by SDNN and RMSSD, but not by RHR. In our sample of young and middle-aged adults, higher MVPA levels over time were associated with better cardiac autonomic function, which explained some of the associations between PA trajectories and better cognition.