Bats and their parasites are increasingly investigated for their role in maintenance and transmission of potentially emerging pathogens. The islands of the western Indian Ocean hold nearly 50 bat species, mostly endemic and taxonomically well studied. However, investigation of associated viral, bacterial, and external parasites has lagged behind. In the case of their ectoparasites, more detailed information should provide insights into the evolutionary history of their hosts, as well as pathogen cycles in these wild animals. Here we investigate species of Nycteribiidae, a family of obligate hematophagous wingless flies parasitizing bats. Using morphological and molecular approaches, we describe fly species diversity sampled on Madagascar and the Comoros for two cave-roosting bat genera with contrasting ecologies: Miniopterus and Rousettus. Within the sampling area, 11 endemic species of insect-feeding Miniopterus occur, two of which are common to Madagascar and Comoros, while fruit-consuming Rousettus are represented by one species endemic to each of these zones. Morphological and molecular characterization of flies reveals that nycteribiids associated with Miniopterus bats comprise three species largely shared by most host species. Flies of M. griveaudi, one of the two bats found on Madagascar and certain islands in the Comoros, belong to the same taxon, which accords with continued over-water population exchange of this bat species and the lack of inter-island genetic structuring. Flies parasitizing Rousettus belong to two distinct species, each associated with a single host species, again in accordance with the distribution of each endemic bat species.