Populations of the desert seed-harvesting ant Phei-dole xerophylla are often characterized by high nest density leading to competitive interactions between foragers from different nests. We investigated the inter-nest aggression, spatial distribution and genetic structure of a P. xerophylla population of the Mojave Desert in Southern California. Inter-nest aggression was quantified by standardized staged encounters in a neutral arena. Genetic relatedness within nests and relatedness between nests were calculated using allelic frequencies at four microsatellite-DNA loci. We found a bimodal distribution of inter-colony aggression levels with a first mode at low aggression levels and another mode at much higher aggression levels. Inter-colony aggression levels were largely non-transitive. No effect of geographical distance on inter-nest aggression levels was detected. Despite high amounts of variation in inter-colony relatedness (-0.24 to 0.37) this variable did not correlate with the level of aggression between nests. Intra-nest relatedness ranged from 0.40 to 0.75 and close inspection of worker genotypes within colonies revealed a high proportion of polygynous colonies or a mixture of polygyny and polyandry. Aggression levels among nests was found to decrease with increasing intra-nest relatedness. These results do not support the idea that aggression is modulated by a nestmate recognition mechanism based on overall genetic similarity. Instead, the absence of transitivity found in inter-colony aggression and bimodal distribution of aggression levels are compatible with a common label acceptance model of nestmate recognition and suggest that label diversity may be encoded by a limited number of loci.