The Great American Biotic Interchange (GABI) is a large-scale zoogeographic event that illustrates the exchange and diversification of mammals between North and South America. This phenomenon was accelerated by the connection of both landmasses during the Pliocene. Support for this phenomenon includes the extant distribution of xenarthrans, didelphiomorph marsupials, hystricognath and cricetine rodents, sciurids and carnivores, as well as the distribution of fossils in the stratigraphic record and the coalescence of genotypes. Contrasting with the relatively well-documented role and history of mammals in GABI, the role of their parasites has been largely neglected. As a consequence, the reconstructions of the causes of diversification, extinction and dispersion of groups of mammals during the Pliocene (and Miocene) invoke changes in climate patterns and the role of competitors or predators, yet in most cases the lines of evidence are not direct. We posit that infections with parasites offer a direct form of evidence of the role of interactions among species, by considering that the successful establishment of species of parasites in new groups of vertebrates will result in a net effect on their adaptive immune system. Thus, the current distribution of nematode parasites of the families Aspidoderidae, Nippostrongylidae, Onchocercidae, Oxyuridae, Rictaluriidae and Viannaidae offers evidence that the historical associations of these nematodes and their hosts diverge from the expected cospeciation and codivergence. Thus, clades of parasites infect disparate clades of mammals and, by deviating from the expected cospeciation, represent a paradox. This paradox deters investigators from studying historical associations among symbionts, since researchers lose the compelling simplicity of testing coevolutionary associations through the congruence of their resulting phylogenies. However, the reconstruction of historical associations must acknowledge the differential survival of parasites in novel hosts. This consideration is part of the Stockholm Paradigm, which includes the hypotheses known as Ecological Fitting, Oscillations, Taxon Pulses and Mosaics of Geographic Coevolution. We introduce nine host-parasite systems that provide insights on the role of parasites in GABI. We posit that the conservatism of parasite resource use, heritability of the adaptive immune system, and the genetic structure of parasites make it possible to elucidate the role of these parasites in GABI.