Two fish fragments from the Middle to Late Maastrichtian of the Island of Gavdos, Greece, are described. One is a caudal portion of an Ichthyodectoidei incertae sedis, which shows some affinities with Saurodon elongatus from the Late Campanian – Early Maastrichtian of Nardo, southern Italy. The other specimen is an isolated skull referred to Enchodus cf. dirus, which is well preserved enough to be included into a phylogenetic analysis of species referred to the genus Enchodus, and subsequently to analyse the biogeograhic signal provided by the cladogram. E. dirus is known in the Late Cretaceous of North America, both in the Western Interior Seaway and on the eastern coast. The occurrence of this lineage is western Tethys and central Tethys is regarded as the result of a vicariant event. Other vicariant events occurred in the Cretaceous between Enchodus species occurring in western and central Tethys respectively. On the other hand, the geographic distribution of several Enchodus species shows ranges extending along North-South axes.