The ability to recognize individuals is common in animals; however, we know little about why the phenotypic variability necessary for individual recognition has evolved in some animals but not others. One possibility is that natural selection favours variability in some social contexts but not in others. Polistes fuscatus wasps have variable facial and abdominal markings used for individual recognition within their complex societies. Here, I explore whether social behaviour can select for variability by examining the relationship between social behaviour and variability in visual features (marking variability) across social wasp taxa. Analysis using a concentrated changes test demonstrates that marking variability is significantly associated with nesting strategy. Species with flexible nest–founding strategies have highly variable markings, whereas species without flexible nest–founding strategies have low marking variability. These results suggest that: (i) individual recognition may be widespread in the social wasps, and (ii) natural selection may play a role in the origin and maintenance of the variable distinctive markings. Theoretical and empirical evidence suggests that species with flexible nesting strategies have reproductive transactions, a type of complex social behaviour predicted to require individual recognition. Therefore, the reproductive transactions of flexible species may select for highly variable individuals who are easy to identify as individuals. Further, selection for distinctiveness may provide an alternative explanation for the evolution of phenotypic diversity.