The study of the polyopisthocotylan parasites of marine fishes in the western Mediterranean is carried on using an integrative approach combining morphology and DNA barcodes. Ktarius patrickbrueli n. gen. n. sp (Polyopisthocotyla, Microcotylidae), from the gills of the pink dentex Dentex gibbosus (Teleostei, Sparidae) from the western Mediterranean Sea off Tunisia, is described. Anatomical and morphological features of the new genus are described, and the molecular barcodes for nuclear and mitochondrial markers (28S rRNA and cox1) are generated. The new genus is closely related to Microcotyle by sharing a symmetrical haptor, inverted question mark-shaped ovary and unarmed vagina. However, Ktarius n. gen. can be distinguished from Microcotyle and other Microcotylinae taxa by an unarmed male copulatory organ, formed by a long muscular cirrus, a basal layer of concentric muscles, and an elongated thick-walled ejaculatory bulb. A partial 28S rDNA sequence of K. patrickbrueli n. gen. n. sp. was obtained and found to be distinct from all known microcotylid sequences, with a p-distance of 5–13%. A phylogenetic tree constructed from available microcotylid sequences revealed that K. patrickbrueli n. gen. n. sp. clustered in a strongly supported clade of Microcotylinae, containing species of Omanicotyle, Bivagina, and Microcotyle confirming its belonging to the Microcotylinae subfamily. The cox1 sequences of K. patrickbrueli n. gen. n. sp. were highly divergent from the closely related genus Pauciconfibula and confirmed its distinction. This new genus is the third polyopisthocotylan genus to be described from sparids of Dentex.