How do social group boundaries evolve? Does the appearance of a new out-group change the in-group’s perceptions of other out-groups? We introduce a conceptual framework of contextdependent categorization, in which exposure to one minority leads to recategorization of other minorities when the former is perceived as more distant than the latter. We test this framework by studying how Mexican immigration to the US affected whites’ attitudes and behaviors towards African Americans. We combine survey and crime data with a differencein-differences design and an instrumental variables strategy. Consistent with the theory, Mexican immigration improves whites’ attitudes towards blacks, increases support for problack government policies and lowers anti-black hate crimes, while simultaneously increasing prejudice against Hispanics. Immigration of groups perceived as less distant than blacks does not have similar effects. Our findings imply that changes in the size of one group can affect the entire web of inter-group relations in diverse societies.