The study of intraspecific variation with respect to host plant utilization in polyphagous insects is crucial for understanding evolutionary patterns of insect-plant interactions. Aphis gossypii (Glover) is a cosmopolitan and extremely polyphagous aphid species. If host plant species or families constitute selective regimes to these aphids, genetic differentiation and host associated adaptation may occur. In this study, we describe the genetic structure of A. gossypii collected in six localities in Tunisia on different vegetable crops, on citrus trees and on Hibiscus. The aim was to determine if the aphid populations are structured in relation to the host plants and if such differentiation is consistent among localities. The genetic variability of A. gossypii samples was examined at eight microsatellite loci. We identified only 11 multilocus genotypes among 559 individuals. Significant deviations from Hardy-Weinberg equilibrium, linkage disequilibria and absence of recombinant genotypes, confirmed that A. gossypii reproduces by continuous apomictic parthenogenesis. Genetic differentiation between localities was not significant, whereas a strong differentiation was observed between host plant families (0.175<FST<0.691). The great majority of aphids exhibited one of three predominant multilocus genotypes that were repeatedly and respectively associated to the three plant families, Cucurbitaceae, Solanaceae and Rutaceae, demonstrating host specialization in A. gossypii. These specialized genotypes were simultaneously found with other clones on Hibiscus, suggesting that this perennial host could act as a refuge plant between two vegetable crop seasons.