Here we report the results of a species level phylogenetic study of Cephaloleia beetles designed to clarify relationships and patterns of host plant taxon and tissue use among species. Our study is based on approximately 1800 bp of mtDNA sequence data (COI, tRNA-Leu, COII) and 400 bp of nDNA sequence data (EF1a). Maximum parsimony, maximum likelihood, and Bayesian methods of phylogenetic inference consistently recover a monophyletic Cephaloleia outside of a basal clade of primarily palm feeding species (the ‘Arecaceae-feeding clade’), Aslamidium spp., and C. irregularis. In all three analyses, the ‘Arecaceae-feeding clade’ includes Cephaloleia spp. with unusual morphological features, and a few species currently placed in other cassidine genera and tribes. All three analyses also recover a clade that includes all Zingiberales feeding Cephaloleia and most Cephaloleia species (the ‘Zingiberales-feeding clade’). Two notable clades are found within the ‘Zingiberales-feeding clade’. One is comprised of beetles that normally feed only on the young rolled leaves of plants in the families Heliconiaceae and Marantaceae (the ‘Heliconiaceae & Marantaceae-feeding clade’). The other is comprised of relative host tissue generalist, primarily Zingiberales feeding species (the ‘generalist-feeding clade’). A few species in the ‘generalist-feeding clade’ utilize Cyperaceae or Poaceae as hosts. Overall, relatively basal Cephaloleia (e.g., the ‘Arecaceae clade’) feed on relatively basal monocots (e.g., Cyclanthaceae and Arecaceae), and relatively derived Cephaloleia (e.g., the ‘Zingiberales-feeding clade’) feed on relatively derived monocots (mostly in the order Zingiberales). Zingiberales feeding and specialization on young rolled Zingiberales leaves have each apparently evolved just once in Cephaloleia.