All people share knowledge of cultural stereotypes of social groups—but what are the origins of these stereotypes? We examined whether stereotypes form spontaneously as information is repeatedly passed from person to person. As information about novel social targets was passed down a chain of individuals, what initially began as a set of random associations evolved into a system that was simplified and categorically structured. Over time, novel stereotypes emerged that not only were increasingly learnable but also allowed generalizations to be made about previously unseen social targets. By illuminating how cognitive and social factors influence how stereotypes form and change, these findings show how stereotypes might naturally evolve or be manipulated.