Gall wasps (Cynipidae) represent the most spectacular radiation of gall-inducing insects. In addition to true gall formers, gall wasps also include phytophagous inquilines, which live inside the galls induced by gall wasps or other insects. Here we present the first comprehensive molecular and total-evidence analyses of higher-level gall wasp relationships. We studied more than 100 taxa representing a rich selection of outgroups and the majority of described cynipid genera outside the diverse oak gall wasps (Cynipini), which were more sparsely sampled. About 5 kb of nucleotide data from one mitochondrial (COI) and four nuclear (28S, LWRh, EF1alpha F1, and EF1alpha F2) markers were analyzed separately and in combination with morphological and life-history data. According to previous morphology-based studies, gall wasps evolved in the Northern Hemisphere and were initially herb gallers. Inquilines originated once from gall inducers that lost the ability to initiate galls. Our results, albeit not conclusive, suggest a different scenario. The first gall wasps were more likely associated with woody host plants, and there must have been multiple origins of gall inducers, inquilines or both. One possibility is that gall inducers arose independently from inquilines in several lineages. Except for these surprising results, our analyses are largely consistent with previous studies. They confirm that gall wasps are conservative in their host-plant preferences, and that herb-galling lineages have radiated repeatedly onto the same set of unrelated host plants. We propose a revised classification of the family into twelve tribes, which are strongly supported as monophyletic across independent datasets. Four are new: Aulacideini, Phanacidini, Diastrophini and Ceroptresini. We present a key to the tribes and discuss their morphological and biological diversity. Until the relationships among the tribes are resolved, the origin and early evolution of gall wasps will remain elusive.