In recent years, molecular studies in host-parasite interactions in terms of coevolution have become important. Larvae (L3) of two species of Contracaecum were found parasitizing species of Rivulidae in the Atlantic coastal basins from Uruguay. The aim of this study is to determine the patterns of differentiation of this host-parasite complex in order to clarify possible coevolutionary events in such interaction throughout phylogeographic approach using both nuclear and mitochondrial molecular markers (internal transcribed spacers (ITS) and cytochrome oxidase subunit 1 (cox-1)). Based on both markers, intraspecific variation in Contracaecum species was lower than 2 %, while interspecific variation was greater than 10 %. Both species of Contracaecum constitute monophyletic groups. Contracaecum resulted in a paraphyletic genus when incorporating other Contracaecum species and closely related nematode sequences from GenBank. ITS regions showed that Contracaecum sp. 1 is more closely related to other species of the same genus than with their counterparts from Atlantic coastal basins in Uruguay. Haplotype network for both markers corroborate the existence of two distinct taxa. While ITS pairwise FST comparisons and the indirect estimate of gene flow confirm the existence of two distinct Contracaecum species, mitochondrial gene detected low levels of migrants between some of the populations from both species. Our results suggest that coevolution in this host-parasite complex species is plausible. Parasite cladogenetic events occur almost simultaneously with the separation of the hypothetical ancestors of each species complex of Austrolebias during Pliocene. Additionally, the two lineages of Contracaecum colonize differently the species within each of the Austrolebias complexes.