The formation of social groups has important impacts on fitness for many animal species, with differences in group compositions resulting in a range of fitness outcomes for individuals. Recent interest in mixed-species grouping, which extends from a large body of literature invested in understanding single-species grouping, highlights novel complexities of group formation which relate to phenotypic, behavioural and physiological differences that naturally exist between species. Among fishes, mixed-species shoaling is a common form of social grouping behaviour displayed across a range of marine and freshwater ecosystems. Research explaining mixed-species shoaling shows some overlap with explanations for single-species shoaling; however, it also demonstrates that distinct differences between species give rise to unique cost-benefit trade-offs which need to be incorporated into conceptual models of mixed-species shoaling behaviour. Unique predation related trade-offs may arise from inefficiency of the confusion effect, variation in vigilance between species and unequal species-preferences shown by predators, whilst unique foraging-related trade-offs may arise from diet partitioning, variations in foraging behaviour and differences in competitive abilities between species. We review the literature on fitness outcomes associated with mixed-species shoaling and present a new theoretical framework to explain the cost-benefit trade-offs for individuals within mixed-species shoals. The framework incorporates both trade-offs arising from differences between species and those arising from group size, the former having been largely ignored due to a focus on single-species shoaling. Our framework is designed to inform future research striving to explain mixed-species shoaling behaviour.