A phylogenetic analysis of the genus Gonioctena (Coleoptera, Chrysomelidae) based on allozyme data (17 loci) and mitochondrial DNA sequence data (three gene fragments, 1,391 sites) was performed to study the evolutionary history of host-plant shifts among these leaf beetles. This chrysomelid genus is characteristically associated with a high number of different plant families. The diverse molecular data gathered in this study are to a large extent congruent, and the analyses provide a well-supported phylogenetic hypothesis to address questions about the evolution of host-plant shifts in the genus Gonioctena. The most-parsimonious reconstruction of the ancestral host-plant associations, based on the estimated phylogeny, suggests that the Fabaceae was the ancestral host-plant family of the genus. Although most of the host-plant shifts (between different host species) in Gonioctena have occurred within the same plant family or within the same plant genus, at least eight shifts have occurred between hosts belonging to distantly related and chemically dissimilar plant families. In these cases, host shifts may have been simply directed toward plant species available in the environment. Yet, given that two Gonioctena lineages have independently colonized the same three new plant families, including four of the same new genera, some constraints are likely to have limited the different possibilities of interfamilial host-plant shifts.