A parasitological investigation of Cyprinella venusta and Notropis cf. stramineus sampled in Texas, USA, in the Guadalupe River, revealed the presence of Gyrodactylus crysoleucas Mizelle and Kritsky, 1967 on C. venusta, and Gyrodactylus mediotorus King, Marcogliese, Forest, McLaughlin & Bentzen, 2013 on both fish species. This represents new leuscicid fish hosts and locality records for these two gyrodactylids. Gyrodactylus crysoleucas previously identified from both non-native Californian Notemigonus crysoleucas and from farmed stocks in Minnesota demonstrated intraspecific variability in terms of morphology and genetics as a local adaptation associated with isolation by distance. Results further confirmed G. crysoleucas as alien in the western USA and suggested host-switching involving C. venusta and N. crysoleucas. Conservative morphology and genetics on the part of G. mediotorus from C. venusta and N. cf. stramineus (Guadalupe River) was observed, while higher genetic divergence in the ITS sequences associated with morphological discrepancy was found between the studied G. mediotorus specimens and those of Notropis hudsonius than when considering the parasites of Notropis texanus. The separation of G. mediotorus into geographical subgroups may indicate ongoing speciation linked to the Pleistocene glaciations in North America, and to hydrographic barriers that facilitated separate evolutionary paths leading to speciation. We suggest that deep investigations of Gyrodactylus populations will help to understand the speciation of these parasites and their adaptation to Nearctic fish hosts.