For the last 40 years, many authors have attempted to characterize the main patterns of plant-insect evolutionary interactions and understand their causes. In the present work on African seed-beetles (Coleoptera: Bruchidae), we have performed a 10-year field work to sample seeds of more than 300 species of potential host-plants (from the family Fabaceae), to obtain bruchids by rearing. This seed sampling in the field was followed by the monitoring of adult emergences which gave us the opportunity to identify host-plant use accurately. Then, by using molecular phylogenetics (on a combined data set of four genes), we have investigated the relationships between host-plant preferences and insect phylogeny. Our objectives were to investigate the level of taxonomic conservatism in host-plant fidelity and host-plant chemistry. Our results indicate that phylogenetically related insects are associated with phylogenetically related host-plants but the phylogeny of the latter cannot alone explain the observed patterns. Major host shifts from Papilionoideae to Mimosoideae subfamilies have happened twice independently suggesting that feeding specialization on a given host-plant group is not always a dead end in seed-beetles. If host-plant taxonomy and chemistry in legumes generally provide consistent data, it appears that the nature of the seed secondary compounds may be the major factor driving the diversification of a large clade specializing on the subfamily Mimosoideae in which host-plant taxonomy is not consistent with chemical similarity.