Obligate brood parasites, which typically lack reliable interactions with conspecifics early in life, acquire species recognition cues by mechanisms other than imprinting on parents and siblings. The African indigobirds (Vidua spp.) are exceptional among brood parasites in that learning and mimicry of host vocalizations play an integral role in the social behavior of the parasites. Male indigobirds have impressive vocal repertoires featuring chatter calls, host mimicry, and complex non-mimicry songs. While chatter calls are similar, sympatric indigobirds are distinguished both by their mimicry of different hosts and by unique repertoires of non-mimicry songs. A previous playback experiment showed that male indigobirds respond differentially to natural singing (i.e. playbacks including host mimicry, chatter, and complex non-mimicry) of sympatric conspecifics and heterospecifics, but the relative role of host mimicry and complex non-mimicry in species recognition remains unknown. We addressed this question in a playback experiment that tested the response of focal males to 3 treatments: sympatric conspecific, allopatric conspecific (same host mimicry combined with unfamiliar complex non-mimicry songs), and sympatric heterospecific (different host mimicry and different, but familiar, complex non-mimicry). Three behavioral responses (number of hops, latency of response, and number of chatter calls) were similar in the 2 conspecific treatments but differed in comparison with the heterospecific treatment. Our study provides evidence that host mimicry is an important cue in species recognition among territorial male indigobirds and suggests that it may contribute to species cohesion when juveniles or adults disperse beyond the boundaries of their local dialect neighborhood. This study enhances our understanding of avian recognition systems by showing that cues obtained through heterospecific imprinting can be important for species recognition in brood parasitic birds.