Internally feeding herbivorous insects such as leaf miners have developed the ability to manipulate the physiology of their host plants in a way to best meet their metabolic needs and compensate for variation in food nutritional composition. For instance, some leaf miners can induce green-islands on yellow leaves in autumn, which are characterized by photosynthetically active green patches in otherwise senescing leaves. It has been shown that endosymbionts, and most likely bacteria of the genus Wolbachia, play an important role in green-island induction in the apple leaf-mining moth Phyllonorycter blancardella. However, it is currently not known how widespread is this moth-Wolbachia-plant interaction. Here, we studied the co-occurrence between Wolbachia and the green-island phenotype in 133 moth specimens belonging to 74 species of Lepidoptera including 60 Gracillariidae leaf miners. Using a combination of molecular phylogenies and ecological data (occurrence of green-islands), we show that the acquisitions of the green-island phenotype and Wolbachia infections have been associated through the evolutionary diversification of Gracillariidae. We also found intraspecific variability in both green-island formation and Wolbachia infection, with some species being able to form green-islands without being infected by Wolbachia. In addition, Wolbachia variants belonging to both A and B supergroups were found to be associated with green-island phenotype suggesting several independent origins of green-island induction. This study opens new prospects and raises new questions about the ecology and evolution of the tripartite association between Wolbachia, leaf miners, and their host plants.