Although heterospecific associations beneficial to one or both species involved (e.g. commensalisms or mutualisms) are common, it is generally assumed that interactions between species are transient and not particular to individuals. However, long-term interactions between individuals of different species do occur. In such heterospecific social groups, discrimination between heterospecific individuals may be beneficial, allowing individuals to direct beneficial or aggressive behaviors towards appropriate targets. Here we describe heterospecific groups composed of splendid and variegated fairy-wrens (Malurus splendens and M. lamberti) and provide the first experimental evidence that recognition of heterospecific group members occurs across species. In these species, family groups live on overlapping territories and co-defend shared territories against both heterospecific and conspecific intruders. Individuals on shared territories were frequently observed traveling and foraging together. Socially dominant males of both species responded more aggressively to songs of neighboring and foreign heterospecific fairy-wrens than they did to those of their co-resident heterospecifics. Although splendid fairy-wrens did not change their behavior when associating with heterospecifics, variegated fairy-wrens spent more time foraging, were less vigilant, had greater first-nest fledging success, and fewer extra-group young. These findings suggest heterospecific associations between these two species benefit the variegated fairy-wren. Our findings are novel and show that recognition and discrimination among individuals, often considered a prerequisite for conspecific cooperation, can occur across species.