The benefits of group living have traditionally been attributed to risk dilution or the efficient exploitation of resources; individuals in social groups may therefore benefit from access to valuable information. If sociality facilitates access to information, then individuals in larger groups may be predicted to solve novel problems faster than individuals in smaller groups. Additionally, larger group sizes may facilitate the subsequent spread of innovations within animal groups, as has been proposed for human societies. We presented a novel foraging task (where a food reward could be accessed by pushing a self-shutting sliding door) to 16 groups of wild, cooperatively breeding Australian magpies, , ranging in size from two to 11 individuals. We found a nonlinear decline in the time taken for the innovative behaviour to emerge with increasing group size, and social information use facilitated the transmission of novel behaviour, with it spreading more quickly in larger than smaller groups. This study provides important evidence for a nonlinear relationship between group size and the emergence of innovation (and its subsequent transmission) in a wild population of animals. Further work investigating the scope and strength of group size-innovation relationships, and the mechanisms underpinning them, will help us understand the potential advantages of living in larger social groups.