It has been demonstrated that physical activity has a small but positive effect on cognition in old age, which suggests that it may be possible to alter the trajectory of age-related cognitive decline. However, our understanding of which aspects of physical activity that are important for modifying cognition remains incomplete. Adopting an exploratory approach in a sample of 115 healthy older adults (65–75 years), the present cross-sectional study used structural equation modelling to investigate the dissociable associations of physical activity (moderate-to-vigorous activity, derived from 7-day accelerometry) and cardiorespiratory fitness (VO2 max, derived from maximal treadmill ergometer test) with multiple latent cognitive abilities (working memory, episodic memory, spatial and verbal reasoning). The results showed a significant positive association between fitness and working memory, when physical activity was statistically controlled for, and a positive association of similar point magnitude between physical activity and episodic memory, when fitness was statistically controlled for, although the latter association did not reach statistical significance. The results add to the foundation for a more careful investigation of the dissociable associations of moderate-to-vigorous physical activity and fitness with cognition in old age, and encourages future research to test the hypothesis that cardiorespiratory fitness benefits working memory via general cerebrovascular effects on grey matter volume, whilst moderate-to-vigorous physical activity benefits episodic memory via effects on neuroplastic processes.