Species richness and abundance of hosts and parasites are often not perfectly correlated. This may be caused by higher parasite than host extinction rates or population declines, but lower parasite discovery effort has also been suggested. The Mexican free-tailed bat Tadarida brasiliensis is one of the most common and widespread vertebrates in the Americas and host to the ectoparasite Primicimex cavernis, for which only 14 literature records from six sites worldwide exist. Here, we confirm a much smaller parasite than host range. Two dedicated field trips revealed two new P. cavernis sites. In Texas, we found 87% out of eight sites negative for P. cavernis. However, this more likely reflects rarity than low discovery effort, because in one large population (>1000 individuals) in Sonora, putatively negative records occurred at only 31% of 16 sampling dates. Currently, live individuals of P. cavernis are known from only one cave in the United States and one in Mexico. Protecting these existing sites is necessary to preserve this charismatic animal but it should not release us from aiming to discover new sites.