The vast majority of species of velvet ants (Hymenoptera: Aculeata: Mutillidae) are ectoparasitoids of immature stages of other aculeate Hymenoptera (bees, wasps and ants). Due to their cryptic, furtive behaviour at the host nesting sites, however, even basic information on their biology, like host use diversity, is still unknown for entire subfamilies, and the known information, scattered in over two centuries of published studies, is potentially hiding tendencies to host specialization across velvet ant lineages. In this review, based on 305 host associations spanning 132 species in 49 genera and 10 main lineages (tribes/subfamilies), we explored patterns of host use in velvet ants. Overall, 15 families and 29 subfamilies of Aculeata are listed as hosts of mutillids, with a strong predominance of Apoidea (bees and apoid wasps: 19 subfamilies and 82.3% of host records). A series of bipartite networks, multivariate analyses and calculations of different indices suggested possible patterns of specialization. Host taxonomic spectrum (number of subfamilies) of velvet ants was very variable and explained by variation in the number of host records. Instead, we found a great variation of network-based host specialization degree and host taxonomic distinctness that did not depend on the number of host records. Differences in host use patterns seemed apparent across mutillid tribes/subfamilies, among genera within several tribes/subfamilies, and to lesser extent within genera. Taxonomic host use variation seemed not dependent on phylogeny. Instead, it was likely driven by the exploitation of hosts with different ecological traits (nest type, larval diet and sociality). Thus, taxonomically more generalist lineages may use hosts that essentially share the same ecological profile. Interestingly, closely related mutillid lineages often show contrasting combinations of host ecological traits, particularly sociality and larval diet, with a more common preference for ground-nesting hosts across most lineages. This review may serve as a basis to test hypotheses for host use evolution in this fascinating family of parasitoids.