Cooperative breeders serve as models to study the evolution of cooperation and altruism, because in these systems individuals forego own reproduction and expend effort for the benefit of others, which cuts across fundamental predictions of the theory of natural selection. Until now, most research on cooperative breeding has focused on the group level, despite the fact that many cooperatively breeding species exhibit multi-level sociality. Here we show that different levels of sociality may simultaneously and interactively influence Darwinian fitness of helpers and breeders. The social structure of the cooperatively breeding cichlid fish Neolamprologus pulcher comprises two distinct levels: individuals form groups and groups cluster in colonies. Our long-term field data show that larger groups enjoy higher survival and productivity. Groups located at higher densities also benefit from better survival chances, but productivity is interactively influenced by density: larger groups benefit from low densities, while small groups are more productive at higher densities. This outcome is likely caused by effects of competition and cooperation between groups. At high densities, groups frequently engage in territorial conflicts, but our additional experiments show that they can also benefit from the anti-predator behaviour of neighbouring groups. For small groups, the benefits of between-group cooperation appear to outweigh the costs of between-group conflict, whereas this does not apply to large groups. Our results highlight that the exclusive focus on within-group cooperation in the study of highly social animals may limit the understanding of the evolutionary mechanisms underlying cooperation and altruism, because the costs and benefits of sociality may greatly vary between different levels of social organisation.