Gall-forming insects provide ideal systems to analyze the evolution of host–parasite interactions and understand the ecological interactions that contribute to evolutionary diversification. Flies in the family Cecidomyiidae represent the largest radiation of gall-forming insects and are characterized by complex trophic interactions with plants, fungal symbionts, and predators. We analyzed the phylogenetic history and evolutionary associations of the North American cecidomyiid genus Asteromyia, which is engaged in a complex and perhaps co-evolving community of interactions with host-plants, fungi, and parasitoids. Mitochondrial gene trees generally support current classifications, but reveal extensive cryptic diversity within the eight named species. Asteromyia likely radiated after their associated host-plants in the Astereae, but species groups exhibit strong associations with specific lineages of Astereae. Evolutionary associations with fungal mutualists are dynamic, however, and suggest rapid and perhaps coordinated changes across trophic levels.