Recent studies of non-social animals have shown that sexually selected traits signal at least one measure of genetic quality: heterozygosity. To determine whether similar cues reveal group quality in more complex social systems, we examined the relationship between territory size, song structure and heterozygosity in the subdesert mesite (Monias benschi), a group-living bird endemic to Madagascar. Using nine polymorphic microsatellite loci, we found that heterozygosity predicted both the size of territories and the structure of songs used to defend them: more heterozygous groups had larger territories, and more heterozygous males used longer, lower-pitched trills in their songs. Heterozygosity was linked to territory size and song structure in males, but not in females, implying that these traits are sexually selected by female choice and/or male-male competition. To our knowledge, this study provides the first direct evidence in any animal that territory size is related to genetic diversity. We also found a positive association between seasonal reproductive success and heterozygosity, suggesting that this heritable characteristic is a reliable indicator of group quality and fitness. Given that heterozygosity predicts song structure in males, and can therefore be determined by listening to acoustic cues, we identify a mechanism by which social animals may assess rival groups, prospective partners and group mates, information of potential importance in guiding decisions related to conflict, breeding and dispersal.