Phytophagous insects with wide host ranges often exhibit host-associated genetic structure. We used microsatellite analysis to assess the population structure of the cotton aphid, Aphis gossypii Glover (Hemiptera: Aphididae), a serious pest on many economically important crops worldwide. We sampled aphids from five host plant species in Iran and detected strong population subdivision, with an overall multilocus FST of 0.191. The matrix of pairwise FST values indicated that differentiation between populations collected from different hosts was significantly stronger than between populations from the same hosts. Host-associated differentiation was further supported by Bayesian clustering analyses, which grouped all samples from cotton together with aubergine, and all samples from cucumber together with pumpkin and hibiscus. This adds to the growing body of evidence that many seemingly generalist aphids are in fact an assemblage of host-specialized lineages. Although we detected a clear genetic signature of clonal reproduction, the genotypic diversity of A. gossypii in Iran is much higher than in other parts of the world. Particularly samples from cotton exhibited a surprisingly high genotypic diversity, suggesting that many lineages on this host are cyclical parthenogens that engage in regular bouts of sexual reproduction.