This study provides the first phylogenetic analysis of a large sample of the two largest genera of seed-beetles, Acanthoscelides Schilsky and Bruchidius Schilsky, which mostly feed on legumes ( Fabaceae). The goal of this study was to investigate evolutionary patterns in relation to biogeography and host-plant associations. We used three mitochondrial molecular markers and parsimony and Bayesian inference methods to reconstruct the phylogeny of 76 species. In addition, we critically reviewed host-plant records in the literature for these two bruchid genera. Our results demonstrated the existence of two major clades, one New World and one largely Old World, which generally correspond to the two genera. Yet, current classification of several species is erroneous, so that both genera as currently defined are paraphyletic. We highlighted a strong trend toward specialization ( with high taxonomic conservatism in host-plant use) exhibited by the two studied genera. However, we showed the existence of several host shifts during the evolution of this group of bruchids. Our phylogenetic hypotheses and our evaluation of host-plant associations both suggest that the two genera have undergone parallel evolution, as they have independently colonized similar host plants in their respective areas of distribution. Our estimation of divergence times indicated a more ancient origin for bruchids than that suggested by the fossil records. Interestingly, the suggested timing of diversification is consistent with the hypothesis of a radiation that could have occurred contemporaneously with the diversification of their legume hosts.