Background: Research on the association between physical inactivity and cognitive decline and dementia is dominated by studies with short-term follow-up, that might be biased by reverse causality. Objective: Investigate the long-term association between physical activity, cognition, and the rate of age-associated cognitive decline. Methods: We investigated the association between late-life physical activity and executive functioning and rate of decline of executive abilities during follow-up of up to 16 years, in 3553 participants of the prospective Rotterdam Study cohort. Measurement took place in 1997–1999, 2002–2004, 2009–2011, and 2014–2015. Results: At baseline (age ± 72 years), higher levels of physical activity were associated with higher levels of executive functioning (adjusted mean difference = 0.03, 95% CI: 0.00 ; 0.06, p = 0.03). This difference remained intact up to 16 years of follow-up. The level of physical activity at baseline was unrelated to the rate of decline of executive abilities over time, in the whole group (adjusted mean difference in change time*physical activity = 0.00, 95% CI: -0.00 ; 0.01, p = 0.31). However, stratification by APOE genotype showed that the accelerated decline of executive abilities observed in those with the ApoE-ε4 allele might be attenuated by higher levels of physical activity in late adulthood (ApoE-ε4 carriers: B time*physical activity = 0.01, 95% CI: 0.00 ; 0.01, p = 0.03). Conclusion: Higher levels of physical activity in late adulthood are related to higher levels of executive functioning, up to 16 years of follow-up. Accelerated decline of executive abilities observed in those with the ApoE-ε4 allele might be mitigated by higher levels of physical activity.