The global body-fossil record of marine 'fishes' from the time interval immediately preceding the Cretaceous-Paleogene Extinction is markedly poor. This deficiency appears to be further exacerbated with regards to offshore and deep-water taxa, obscuring our understanding of the state and composition of corresponding vertebrate faunas at the onset of this major extinction event. Recent fieldwork in the mid-late Maastrichtian exposures of the Pindos Unit in Gavdos Island, Greece, yielded a small but informative sample of fossil 'fishes', which inhabited the Tethys approximately three to four million years before the extinction. In this work we describe this sample, which comprises between eight and nine discrete morphotypes of various size classes, belonging to †Ichthyodectoidei, Aulopiformes (†Dercetidae, †Enchodontidae, †Ichthyotringidae), cf. †Sardinioididae, as well as the hexanchid shark †Gladioserratus sp. The new material expands the faunal list for the Maastrichtian of Gavdos Island, and the Pindos Unit as a whole, and further allows for the description of a new genus and species of †Enchodontidae and a new species of †Ichthyotringidae. The two new taxa are found to be widespread in the Maastrichtian of the Pindos Unit. The overall character of the assemblage agrees with previous interpretations of an offshore and rather deep depositional environment for the fossiliferous horizons. Furthermore, it exhibits a higher diversity than, and little taxonomic overlap with penecontemporaneous teleost assemblages from the Tethys, and informs on the otherwise poorly known Maastrichtian offshore and deep-water marine ichthyofaunas of the region.