It has become increasingly clear that a larger brain can confer cognitive benefits. Yet not all of the numerous aspects of cognition seem to be affected by brain size. Recent evidence suggests that some more basic forms of cognition, for instance colour vision, are not influenced by brain size. We therefore hypothesize that a larger brain is especially beneficial for distinct and gradually more complex aspects of cognition. To test this hypothesis, we assessed the performance of brain size selected female guppies (Poecilia reticulata) in two distinct aspects of cognition that differ in cognitive complexity. In a standard reversal-learning test we first investigated basic learning ability with a colour discrimination test, then reversed the reward contingency to specifically test for cognitive flexibility. We found that large-brained females outperformed small-brained females in the reversed-learning part of the test but not in the colour discrimination part of the test. Large-brained individuals are hence cognitively more flexible, which probably yields fitness benefits, as they may adapt more quickly to social and/or ecological cognitive challenges. Our results also suggest that a larger brain becomes especially advantageous with increasing cognitive complexity. These findings corroborate the significance of brain size for cognitive evolution.