It has recently become clear that some language-specific traits previously thought to be unique to humans (such as the capacity to combine sounds) are widespread in the animal kingdom. Despite the increase in studies documenting the presence of call combinations in non-human animals, factors promoting this vocal trait are unclear. One leading hypothesis proposes that communicative complexity co-evolved with social complexity owing to the need to transmit a diversity of information to a wider range of social partners. The Western Australian magpie (Gymnorhina tibicen dorsalis) provides a unique model to investigate this proposed link because it is a group-living, vocal learning species that is capable of multi-level combinatoriality (independently produced calls contain vocal segments and comprise combinations). Here, we compare variations in the production of call combinations across magpie groups ranging in size from 2 to 11 birds. We found that callers in larger groups give call combinations: (i) in greater diversity and (ii) more frequently than callers in smaller groups. Significantly, these observations support the hypothesis that combinatorial complexity may be related to social complexity in an open-ended vocal learner, providing an important step in understanding the role that sociality may have played in the development of vocal combinatorial complexity.