Physical activity (PA) has been hypothesized to be effective to maintaining cognitive function and delay cognitive decline in the elderly, but physical fitness (PF) could be a better predictor of cognitive function. We aimed to study the association between PA and PF with cognitive function and quality of life using cross-sectional data from 6874 participants of the PREDIMED-Plus trial (64.9 ± 4.9 years, 48.5% female). PF and PA were measured with a Chair Stand Test, the REGICOR and Rapid Assessment Physical Activity questionnaires. Cognitive function was measured with Mini-mental State Examination, Control Oral Word Association Test, Trail Making Test and Digit Span tests; whereas health-related quality of life was assessed with the SF36-HRQL test. Cognitive and quality of life scores were compared among PF quartiles and PA levels (low, moderate and high) with ANCOVA and with Chair Stand repetitions and energy expenditure from total PA with multivariable linear regression adjusted for confounding factors. PF associated with higher scores in phonemic and semantic verbal fluency tests and with lower TMT A time. However, PA was not associated with the neurocognitive parameters evaluated. Both PF and PA levels were strongly associated with a better quality of life. We concluded that PF, but not PA, is associated with a better cognitive function. This trial was retrospectively registered at the International Standard Randomized Controlled Trial (ISRCTN89898870, https://www.isrctn.com/ISRCTN89898870?q=ISRCTN89898870&filters=&sort=&offset=1&totalResults=1&page=1&pageSize=10&searchType=basic-search) on 07/24/2014.