Cooperative breeders serve as a model to study the evolution of cooperation, where costs and benefits of helping are typically scrutinized at the level of group membership. However, cooperation is often observed in multi-level social organizations involving interactions among individuals at various levels. Here, we argue that a full understanding of the adaptive value of cooperation and the evolution of complex social organization requires identifying the effect of different levels of social organization on direct and indirect fitness components. Our long-term field data show that in the cooperatively breeding, colonial cichlid fish Neolamprologus pulcher, both large group size and high colony density significantly raised group persistence. Neither group size nor density affected survival at the individual level, but they had interactive effects on reproductive output; large group size raised productivity when local population density was low, whereas in contrast, small groups were more productive at high densities. Fitness estimates of individually marked fish revealed indirect fitness benefits associated with staying in large groups. Inclusive fitness, however, was not significantly affected by group size, because the direct fitness component was not increased in larger groups. Together, our findings highlight that the reproductive output of groups may be affected in opposite directions by different levels of sociality, and that complex forms of sociality and costly cooperation may evolve in the absence of large indirect fitness benefits and the influence of kin selection.