Weevils are an unusually species-rich group of phytophagous insects for which there is increasing evidence of frequent involvement in brood-site pollination. This study examines phylogenetic patterns in the emergence of brood-site pollination mutualism among one of the most speciose beetle groups, the flower weevils (subfamily Curculioninae). We analysed a novel phylogenomic dataset consisting of 214 nuclear loci for 202 weevil species, with a sampling that mainly includes flower weevils as well as representatives of all major lineages of true weevils (Curculionidae). Our phylogenomic analyses establish a uniquely comprehensive phylogenetic framework for Curculioninae and provide new insights into the relationships among lineages of true weevils. Based on this phylogeny, statistical reconstruction of ancestral character states revealed at least 10 independent origins of brood-site pollination in higher weevils through transitions from ancestral associations with reproductive structures in the larval stage. Broadly, our results illuminate the unexpected frequency with which true weevils—typically specialized phytophages and hence antagonists of plants—have evolved mutualistic interactions of ecological significance that are key to both weevil and plant evolutionary fitness and thus a component of their deeply intertwined macroevolutionary success.