The range of hosts exploited by a parasite is determined by several factors, including host availability, infectivity and exploitability. Each of these can be the target of natural selection on both host and parasite, which will determine the local outcome of interactions, and potentially lead to coevolution. However, geographical variation in host use and specificity has rarely been investigated. Maculinea (=Phengaris) butterflies are brood parasites of Myrmica ants that are patchily distributed across the Palæarctic and have been studied extensively in Europe. Here, we review the published records of ant host use by the European Maculinea species, as well as providing new host ant records for more than 100 sites across Europe. This comprehensive survey demonstrates that while all but one of the Myrmica species found on Maculinea sites have been recorded as hosts, the most common is often disproportionately highly exploited. Host sharing and host switching are both relatively common, but there is evidence of specialization at many sites, which varies among Maculinea species. We show that most Maculinea display the features expected for coevolution to occur in a geographic mosaic, which has probably allowed these rare butterflies to persist in Europe.