Most aphids are highly specialized on one or two related plant species and generalist species often include sympatric populations adapted to different host plants. Our aim was to test the hypothesis of the existence of host specialized lineages of the aphid Melanaphis sacchari in Reunion Island. To this end, we investigated the genetic diversity of the aphid and its association with host plants by analyzing the effect of wild sorghum Sorghum bicolor subsp. verticilliflorum or sugarcane as host plants on the genetic structuring of populations and by performing laboratory host transfer experiments to detect trade-offs in host use. Genotyping of 31 samples with 10 microsatellite loci enabled identification of 13 multilocus genotypes (MLG). Three of these, Ms11, Ms16 and Ms15, were the most frequent ones. The genetic structure of the populations was linked to the host plants. Ms11 and Ms16 were significantly more frequently observed on sugarcane, while Ms15 was almost exclusively collected in colonies on wild sorghum. Laboratory transfer experiments demonstrated the existence of fitness trade-offs. An Ms11 isofemale lineage performed better on sugarcane than on sorghum, whereas an Ms15 lineage developed very poorly on sugarcane, and two Ms16 lineages showed no significant difference in performances between both hosts. Both field and laboratory results support the existence of host plant specialization in M. sacchari in Reunion Island, despite low genetic differentiation. This study illustrates the ability of asexual aphid lineages to rapidly undergo adaptive changes including shifting from one host plant to another.