Inherited bacteria that kill male hosts early in their development are known from five insect orders. We ask to what extent the incidence of male-killers might be restricted by the rate at which new host-parasite interactions arise, by testing whether multiple male-killers have invaded a single host species. In Uganda, the butterflies Acraea encedon and A. encedana are both infected by the same strain of male-killing Wolbachia and there was no evidence of variation within the population. In Tanzanian A. encedon however, two phylogenetically distinct strains of male-killing Wolbachia were found within the same population. If this pattern of male-killer polymorphism is found to be general across infected species, it suggests that new male-killing infections arise frequently on an evolutionary time scale. Whether this polymorphism is stable, and what forces may be maintaining it, are unknown.