Understanding the interplay between cooperation and conflict in social groups is a major goal of biology. One important factor is genetic relatedness, and animal societies are usually composed of related but genetically different individuals, setting the stage for conflicts over reproductive allocation. Recently, however, it has been found that several ant species reproduce predominantly asexually. Although this can potentially give rise to clonal societies, in the few well-studied cases, colonies are often chimeric assemblies of different genotypes, due to worker drifting or colony fusion. In the ant Cerapachys biroi, queens are absent and all individuals reproduce via thelytokous parthenogenesis, making this species an ideal study system of asexual reproduction and its consequences for social dynamics. Here, we show that colonies in our study population on Okinawa, Japan, recognize and effectively discriminate against foreign workers, especially those from unrelated asexual lineages. In accord with this finding, colonies never contained more than a single asexual lineage and average pairwise genetic relatedness within colonies was extremely high (r = 0.99). This implies that the scope for social conflict in C. biroi is limited, with unusually high potential for cooperation and altruism.