Despite the strong interest in connecting social complexity and cognitive ability, there remains considerable debate about how to best quantify both cognitive performance and social complexity. Measuring group and brain size are clearly not sufficient and recent attention has been placed on the use of rigorous, increasingly challenging cognitive tasks and studying the quality, not merely the number of social interactions. Here we used two cichlid fishes from Lake Tanganyika, one cooperative breeder and one biparental species, in a cross-fostering experiment, to investigate the links between social complexity and cognition. While controlling for parental cues, individual fish grew up either in a socially homogenous group with only conspecifics or in a mixed and diverse social group with hetero- as well as conspecifics and then were tested for learning abilities as subadults. To quantify differences in learning, we first employed a discrimination learning task followed by a reversal learning task that requires behavioral flexibility, as previous associations are forgotten and new associations forged. We found that individuals growing up in a more diverse social environment learned faster and made fewer mistakes in the discrimination learning task, but this ability did not transfer to the reversal learning task. Irrespective of the early social experiences, the cooperatively breeding, and thus the more social of the two cichlid species, learnt the color discrimination more quickly and made significantly fewer errors. These results provide a first demonstration of a possible association between cognitive performance and social complexity in cichlid fishes.