In this study, we have investigated the limits of taxonomic conservatism in host-plant use in the seed-beetle genus Bruchus. To reconstruct the insect phylogeny, parsimony and multiple partitioned Bayesian inference analyses were conducted on a combined data set of four genes. Permutation tests and both global and local maximum-likelihood optimizations of host preferences at distinct taxonomic levels revealed that host-fidelity is still discernible beyond the host-plant tribe level, suggesting the existence of more important than previously thought evolutionary constraints, which are further discussed in details. Our tree topologies are also mostly consistent with extant taxonomic groups. Through the analysis of this empirical data set we also provide meaningful insights on two methodological issues. First, Bayesian inference analyses suggest that partitioning by using codon positions greatly increase the accuracy of phylogenetical reconstructions. Regarding reconstruction of ancestral character states through maximum likelihood, the present study also highlights the usefulness of local optimizations. The issue of over-parameterization is also addressed, as the optimizations with the most parameter-rich models have returned the most counterintuitive results.