Eusocial species, animals which live in colonies with a reproductive division of labor, typically have closed societies, in which colony members are allowed entry and nonmembers, including animals of the same species, are excluded. This implies an ability to discriminate colony members ("self") from nonmembers ("nonself"). We draw analogies between this type of discrimination and MHC-mediated cellular recognition in vertebrates. Recognition of membership in eusocial colonies is typically mediated by differences in the surface chemistry between members and nonmembers and we review studies which support this hypothesis. In rare instances, visual signals mediate recognition. We highlight the need for better understanding of which surface compounds actually mediate recognition and for further work on how differences between colony members and nonmembers are perceived.