Understanding how populations are structured in space and time is a central question in evolutionary biology. Parasites and their hosts are assumed to evolve together, however, detailed understanding of mechanisms leading to genetic structuring of parasites and their hosts are lacking. As a parasite depends on its host, studying the genetic structure of both parasite and host can reveal important insights into these mechanisms. Here, genetic structure of the monogenean parasite Gyrodactylus thymalli and its host the European grayling (Thymallus thymallus) was investigated in 10 tributaries draining into the large Lake Mjøsa in Norway. The population genetic structure of spawning grayling was studied using microsatellite genotyping, while G. thymalli was studied by sequencing a mitochondrial DNA gene (dehydrogenase subunit 5). Two main genetic clusters were revealed in grayling, one cluster comprising grayling from the largest spawning population, while the remaining tributaries formed the second cluster. For both taxa, some genetic differentiation was observed among tributaries, but there was no clear isolation-by-distance signature. The structuring was stronger for the host than for the parasite. These results imply that moderate to high levels of gene flow occur among the sub-populations of both taxa. The high parasite exchange among tributaries could result from a lack of strong homing behavior in grayling as well as interactions among individual fish outside of the spawning season, leading to frequent mixing of both host and parasite.