In melon, the Vat gene confers resistance to colonization by the Cotton-Melon aphid species, Aphis gossypii Glover. The Vat gene has been present in several melon varieties produced in south-eastern France for the past fifteen years, although as time goes by, the risk of the aphids overcoming such resistance is increasing. The study of the genetic structure of Cotton-Melon aphid populations is important in order to understand the efficacy and durability of methods to control pests through the use of resistant plants. Therefore, as outlined in the present paper, we set up field trials in geographically distant melon-producing areas in France and the French West Indies (FWI) using melon plants with the resistant allele or with the susceptible allele at the Vat locus. Samples of A. gossypii were collected from these crops in the different regions and their genetic diversity analyzed at eight microsatellite loci. We identified 33 multilocus genotypes (MLGs) that were present in multiple copies, of which five were observed in several regions of France whilst two were restricted to the FWI. The genetic diversity was high in south-eastern France, moderate in south-western and western France, and low in Guadeloupe (FWI). Differentiation between pairs of geographical populations in mainland France estimated by multilocus FST was not significant. Some MLGs (NM1 and C9) were significantly less frequent on melon with the resistant allele at the Vat locus than on melon with the susceptible allele at the Vat locus, while the frequencies of others (C6, CUC1, CUC13 and CUC25) increased significantly on melon plants with the resistant allele at the Vat locus.