The Polystomatidae is the only family within the Monogenea to parasitize sarcopterygians such as the Australian lungfish Neoceratodus poisteri and freshwater tetrapods (lissamphibians and chelonians). We present a phylogeny based on partial 18S rDNA sequences of 26 species of Polystomatidae and three taxon from the infrasubclass Oligonchoinea (= Polyopisthocotylea) obtained from the gills of teleost fishes. The basal position of the polystome from lungfish within the Polystomatidae suggests that the family arose during the evolutionary transition between actinopterygians and sarcopterygians, ca. 425 million years (Myr) ago. The monophyly of the polystomatid lineages from chelonian and lissamphibian hosts, in addition to estimates of the divergence times, indicate that polystomatids from turtles radiated ca. 191 Myr ago, following a switch from an aquatic amniote presumed to be extinct to turtles, which diversified in the Upper Triassic. Within polystomatids from lissamphibians, we observe a polytomy of four lineages, namely caudatan, neobatrachian, pelobatid and pipid polystomatid lineages, which occurred ca. 246 Myr ago according to molecular divergence-time estimates. This suggests that the first polystomatids of amphibians originated during the evolution and diversification of lissamphibian orders and suborders ca. 250 Myr ago. Finally, we report a vicariance event between two major groups of neobatrachian polystomes, which is probably linked to the separation of South America from Africa ca. 100 Myr ago.