The beetle genus Cephaloleia has evolved in association with tropical ginger plants and for many species their specific host plant associations are known. Here we show that the core microbiome of six closely related Costa Rican Cephaloleia species comprises only eight bacterial groups, including members of the Acinetobacter, Enterobacteriacea, Pseudomonas, Lactococcus, and Comamonas. The Acinetobacter and Enterobacteriacea together accounted for 35% of the total average 16S rRNA ribotypes recovered from all specimens. Further, microbiome diversity and community structure was significantly linked to beetle diet breadth, between those foraging on less than two plant types (specialists) versus over nine plant types (generalists). Moraxellaceae, Enterobacteriaceae, and Pseudomonadaceae were highly prevalent in specialist species, and also present in eggs, while Rickettsiaceae associated exclusively with generalist beetles. Bacteria isolated from Cephaloleia digestive systems had distinct capabilities and suggested a possible beneficial role in both digestion of plant-based compounds, including xylose, mannitol, and pectin, and possible detoxification, via lipases. Cephaloleia species are currently expanding their diets to include exotic invasive plants, yet it is unknown whether their microbial community plays a role in this transition. In this study, colonization of invasive plants was correlated with a dysbiosis of the microbiome, suggesting a possible relationship between gut bacteria and niche adaptation.