A survey of the gill parasites of Epinephelus costae (Teleostei: Serranidae) was conducted between 2001 and 2005 in the Gulf of Gabès (Tunisia). Five new species of Diplectanidae (Monogenea) were collected, all belonging to Pseudorhabdosynochus Yamaguti, 1958: P. bouaini sp. n., P. dolicocolpos sp. n., P. enitsuji sp. n., P. sinediscus sp. n., and P. sosia sp. n. These five species differ from each other and from all described species of Pseudorhabdosynochus by the morphology and size of their sclerotized vagina. These diplectanids (except P. sinediscus) were also collected from the same host off Dakar in 1981 and 1989. The present paper includes the descriptions and taxonomic considerations of each of these species in addition to an amended diagnosis of Pseudorhabdosynochus. A key to the five new species parasitizing E. costae is provided. These five species are the first diplectanids described from E. costae.