Specimens of Gyrodactylus corleonis Paladini, Cable, Fioravanti, Faria & Shinn, 2010 (Monogenea: Gyrodactylidae) were collected from the body and fins of Gobius cobitis Pallas in the western Mediterranean Sea off northwestern Sardinia. This is the first finding of this species in the wild and also represents a new host record. A morphological comparison of the new material with the type description of G. corleonis is presented. Since G. corleonis was found in the wild on representatives of the Gobiidae, a comparison with species of Gyrodactylus von Nordmann, 1832 parasitising gobies is included. The occurrence of G. corleonis on different host species and its phylogenetic relationships with gyrodactylids from sand gobies are discussed.