Recent studies have emphasized the role of social learning and cultural transmission in promoting conformity and uniformity in animal groups, but little attention has been given to the role of negative frequency-dependent learning in impeding conformity and promoting diversity instead. Here we show experimentally that under competitive conditions, that are common in nature, social foragers (although capable of social learning) are likely to develop diversity in foraging specialization rather than uniformity. Naïve house sparrows that were introduced into groups of foraging specialists did not conform to the behaviour of the specialists but, rather, learned to use the alternative food-related cues, thus forming groups of complementary specialists. We further show that individuals in such groups may forage more effectively in diverse environments. Our results suggest that when the benefit from socially acquired skills diminishes through competition in a negative frequency-dependent manner, animal societies will become behaviourally diverse rather than uniform.