Insect herbivores frequently cospeciate with symbionts that enable them to survive on nutritionally unbalanced diets. While ancient symbiont gain and loss events have been pivotal for insect diversification and feeding niche specialization, evidence of recent events is scarce. We examine the recent loss of nutritional symbionts (in as little as 1 MY) in sap-feeding Pariaconus, an endemic Hawaiian insect genus that has undergone adaptive radiation, evolving various galling and free-living ecologies on a single host-plant species, Metrosideros polymorpha within the last ∼5 MY. Using 16S rRNA sequencing, we investigated the bacterial microbiomes of 19 Pariaconus species and identified distinct symbiont profiles associated with specific host-plant ecologies. Phylogenetic analyses and metagenomic reconstructions revealed significant differences in microbial diversity and functions among psyllids with different host-plant ecologies. Within a few millions of years, Pariaconus species convergently evolved the closed-gall habit twice. This shift to enclosed galls coincided with the loss of the Morganella-like symbiont that provides the essential amino acid arginine to free-living and open-gall sister species. After the Pariaconus lineage left Kauai and colonized younger islands, both open- and closed-gall species lost the Dickeya-like symbiont. This symbiont is crucial for synthesizing essential amino acids (phenylalanine, tyrosine, and lysine) as well as B vitamins in free-living species. The recurrent loss of these symbionts in galling species reinforces evidence that galls are nutrient sinks and, combined with the rapidity of the evolutionary timeline, highlights the dynamic role of insect-symbiont relationships during the diversification of feeding ecologies. We propose new Candidatus names for the novel Morganella-like and Dickeya-like symbionts.