This study assessed the association of fitness and fatness with cognitive function in women with fibromyalgia, and the independent influence of their single components on cognitive tasks. A total of 468 women with fibromyalgia were included. Speed of information processing and working memory (Paced Auditory Serial Addition Task), as well as immediate and delayed recall, verbal learning and delayed recognition (Rey Auditory Verbal Learning Test) were assessed. Aerobic fitness, muscle strength, flexibility and motor agility were assessed with the Senior Fitness Test battery. Body mass index, percent body fat, fat-mass index and waist circumference were measured. Aerobic fitness was associated with attention and working memory (all, p<0.05). All fitness components were generally associated with delayed recall, verbal learning and delayed recognition (all, p<0.05). Aerobic fitness showed the most powerful association with attention, working memory, delayed recall and verbal learning, while motor agility was the most powerful indicator of delayed recognition. None of the fatness parameters were associated with any of the outcomes (all, p>0.05). Our results suggest that fitness, but not fatness, is associated with cognitive function in women with fibromyalgia. Aerobic fitness appears to be the most powerful fitness component regarding the cognitive tasks evaluated.