Cuckoo wasps (Hymenoptera: Chrysididae) are a species-rich family of obligate brood parasites (i.e. parasitoids and kleptoparasites) whose hosts range from sawflies, wasps and bees, to walking sticks and moths. Their brood parasitic lifestyle has led to the evolution of fascinating adaptations, including chemical mimicry of host odours by some species. Long-term nomenclatural stability of the higher taxonomic units (e.g. genera, tribes, and subfamilies) in this family and a thorough understanding of the family's evolutionary history critically depend on a robust phylogeny of cuckoo wasps. Here we present the results from phylogenetically analysing ten nuclear-encoded genes and one mitochondrial gene, all protein-coding, in a total of 186 different species of cuckoo wasps representing most major cuckoo wasp lineages. The compiled data matrix comprised 4946 coding nucleotide sites and was phylogenetically analysed using classical maximum-likelihood and Bayesian inference methods. The results of our phylogenetic analyses are mostly consistent with earlier ideas on the phylogenetic relationships of the cuckoo wasps' subfamilies and tribes, but cast doubts on the hitherto hypothesized phylogenetic position of the subfamily Amiseginae. However, the molecular data are not fully conclusive in this respect due to low branch support values at deep nodes. In contrast, our phylogenetic estimates clearly indicate that the current systematics of cuckoo wasps at the genus level is artificial. Several of the currently recognized genera are para- or polyphyletic (e.g. Cephaloparnops, Chrysis, Chrysura, Euchroeus, Hedychridium, Praestochrysis, Pseudochrysis, Spintharina, and Spinolia). At the same time, our data support the validity of the genus Colpopyga, previously synonymized with Hedychridium. We discuss possible solutions for how to resolve the current shortcomings in the systematics of cuckoo wasp genera and decided to grant Prospinolia the status of a valid genus (Prospinolia stat.n.) and transferring Spinolia theresae [du Buysson 1900] from Spinolia to Prospinolia (Prospinolia theresae stat.restit.). We discuss the implications of our phylogenetic inferences for understanding the evolution of host associations in this group. The results of our study not only shed new light on the evolutionary history of cuckoo wasps, but also set the basis for future phylogenomic investigations on this captivating group of wasps by guiding taxonomic sampling efforts and the design of probes for target DNA enrichment approaches.