Host quality is critical for parasites. The common cuckoo Cuculus canorus is a generalist avian brood parasite, but individual females show strong preference for a specific host species. Here, we use three extensive datasets to investigate different host characteristics determining cuckoo host selection at the species level: (i) 1871 population-specific parasitism rates collected across Europe; (ii) 14 K cases of parasitism in the United Kingdom; and (iii) 16 K cases of parasitism in Germany, with data collected during the period 1735-2013. We find highly consistent effects of the different host species traits across our three datasets: the cuckoo prefers passerine host species of intermediate size that breed in grass- or shrubland and that feed their nestlings with insects, and avoids species that nest in cavities. Based on these results, we construct a novel host suitability index for all passerine species breeding in Europe, and show that host species known to have a corresponding cuckoo host race (gens) rank among the most suitable hosts in Europe. The distribution of our suitability index shows that host species cannot be classified as suitable or not but rather range within a continuum of suitability.