Kin selection predicts that helpers in cooperative systems should preferentially aid relatives to maximize fitness. In family-based groups, this can be accomplished simply by assisting all group members. In more complex societies, where large numbers of kin and non-kin regularly interact, more sophisticated kin-recognition mechanisms are needed. Bell miners (Manorina melanophrys) are just such a system where individuals regularly interact with both kin and non-kin within large colonies. Despite this complexity, individual helpers of both sexes facultatively work harder when provisioning the young of closer genetic relatedness. We investigated the mechanism by which such adaptive discrimination occurs by assessing genetic kinship influences on the structure of more than 1900 provisioning vocalizations of 185 miners. These 'mew' calls showed a significant, positive linear increase in call similarity with increasing genetic relatedness, most especially in comparisons between male helpers and the breeding male. Furthermore, individual helping effort was more heavily influenced by call similarity to breeding males than to genetic relatedness, as predicted if call similarity is indeed the rule-of-thumb used to discriminate kin in this system. Individual mew call structure appeared to be inflexible and innate, providing an effective mechanism by which helpers can assess their relatedness to any individual. This provides, to our knowledge, the first example of a mechanism for fine-scale kin discrimination in a complex avian society.