African Great Lakes and their fauna are among the prime model systems for evolutionary research. Lake Tanganyika is the second deepest lake in the world and its permanently stratified, relatively species-poor and well-delimited pelagic zone offers a simple model for ecosystem dynamics of open water areas worldwide. In our study, we focused on mitogenomic differentiation of directly transmitted parasites (Monogenea, Kapentagyrus) infecting two species of pelagic clupeid fishes across two subbasins of Lake Tanganyika, to unravel patterns of migration and population dynamics in the pelagic zone of large water bodies. Starting from pooled population samples, altogether containing more than 800 specimens, we provide the first population-genomic study on any parasite in the African Great Lakes. Our results indicate a lack of spatial population structuring in Kapentagyrus tanganicanus infecting its two clupeid hosts. In Kapentagyrus limnotrissae, a parasite specific to only one of the two clupeid hosts, spatial and seasonal restriction in gene flow are observed. Contrasting patterns in spatial population structuring between K. tanganicanus and K. limnotrissae reflect their differences in host range and in the life histories, migration and habitat preference of their respective hosts. This is a proof-of-concept of how parasites can be reliable tags for hardly traceable hosts, in this case indicating host and parasite connectivity throughout the hosts’ spatial distribution. Comparison of population-genetic parameters based on individual specimens versus pooled samples proofs PoolSeq as a suitable method in (mito)genomics of minute taxa that are hard to access in the field.