Sharks (765 specimens from ten species) from the Mediterranean Sea off Algiers, Algeria, were examined for the presence of gill monogeneans. The following deep-sea sharks were investigated from 2009 to 2015: Centrophorus granulosus (27 specimens); Centrophorus uyato (39); Etmopterus spinax (67); Somniosus rostratus (19); Galeus melanostomus (189); Scyliorhinus canicula (261), Hexanchus griseus 3), and Dalatias licha (100). In addition, two pelagic shark species were examined: Alopias vulpinus (7), and Prionace glauca (53). Only two species of gill monogeneans were found. Protocotyle grisea (Cerfontaine, 1899) Euzet et Maillard, 1974 was found on its type-host Hexanchus griseus; comparative measurements are provided, and Algeria is a new geographic record. Squalonchocotyle euzeti n. sp. from Dalatias licha is described here. We found that the species of Squalonchocotyle Cerfontaine, 1899 can be separated into two groups, according to body size. Small-bodied species include 7 species. Large-bodied species (body > 20mm) include S. borealis (Van Beneden, 1853), S. laymani Yamaguti, 1958 and S. euzeti n. sp; the latter is distinguished from the two other species by a characteristically slender body. A sequence of Cytochrome Oxidase Type I (COI) gene, potentially useful for barcoding, was obtained for S. euzeti n. sp. and is the first for the family Hexabothriidae.