Studying the population genetic structure of both parasites and their host-plants is expected to yield new valuable insights into their coevolution. In this study, we examined and compared the population genetic diversity and structure of 12 populations of the Rhus gall aphid, Schlechtendalia chinensis, and its host-plant, Rhus chinensis, using amplified fragment length polymorphism (AFLP) markers. AMOVA analysis showed that the genetic variance of the aphid and its host-plant were both higher within populations compared to that among them, suggesting that a co-evolutionary history has yielded similar patterns of population genetic structure. We did not detect significant correlation between genetic and geographic distance for either the aphid or host-plant populations, therefore rejecting an isolation by distance model for the demographic histories of the two species. However, our results appeared to suggest that genetically diverse host -plant Rhus populations correlated to similarly genetically diverse populations of gall aphid parasites.