We investigated the Gyrodactylus ectoparasites on relict fishes in the isolated endorheic Central Asian Internal drainage basin in Mongolia (The Hollow) and placed them into the global phylogenetic framework based on internal transcribed spacer regions of the nuclear ribosomal DNA (ITS). Much of the rich Pliocene lacustrine ichthyofauna is extinct. We sampled five riverine survivors: Altai osmans Oreoleuciscus humilis and O. potanini (Leuciscidae), Mongolian grayling Thymallus brevirostris (Salmonidae), and stone loaches Barbatula conilobus and B. cobdonensis (Nemacheilidae). We found eight species of the subgenus Gyrodactylus (Limnonephrotus) and four of G. (Gyrodactylus). Nine species were identified as taxa described earlier, and three were described as new. The endemic Mongolian grayling carried four species, only one of wageneri group typical to salmonids (Gyrodactylus radimi sp. nov.), two of nemachili group (G. zavkhanensis sp. nov., G. pseudonemachili Ergens and Bychowsky, 1967), and G. amurensis Akhmerov, 1952 of subgenus G. (Gyrodactylus). G. pseudonemachili was also found on osman and loach. A parasite clade typical for Nemacheilidae was overrepresented by five species (G. tayshirensis sp. nov. on Barbatula conilobus, G. mongolicus Ergens and Dulmaa, 1970, G. nemachili Bychowsky, 1936). Relaxed host specificity mentioned already by Ergens and Dulmaa was evident. In the updated global ITS phylogenies of the two freshwater-restricted subgenera, the parasites from the Mongolian relict populations assumed positions concordant with a hypothesis of multiple ancient introductions from the Euro-Siberian fauna, strong rarefaction and three cases of endemic divergence.