Relatively little is known about what determines whether a heterogenous population ends up in a cooperative or divisive situation. This paper proposes a theoretical model to understand what social structures arise in heterogeneous populations. Individuals face a trade-off between cultural and economic incentives: an individual prefers to maintain his cultural practices, but doing so can inhibit interaction and economic exchange with those who adopt different practices. We find that a small minority group will adopt majority cultural practices and integrate. In contrast, minority groups above a certain critical mass, may retain diverse practices and may also segregate from the majority. The size of this critical mass depends on the cultural distance between groups, the importance of culture in day to day life, and the costs of forming a social tie. We test these predictions using data on migrants to the United States in the era of mass migration, and find support for the existence of a critical mass of migrants above which social structure in heterogeneous populations changes discretely towards cultural distinction and segregation.