The syllid fauna of three locations in Crete and Israel (Eastern Mediterranean Sea) was studied, yielding 82 syllid species, many of which were found for the first time in the respective areas: Seventeen species were recorded for the first time on the Israeli coasts and 20 in Greek waters. Perkinsyllis augeneri (Hartmann-Schröder, 1979) and Prosphaerosyllis chauseyensis Olivier et al., 2011 are new records for the Mediterranean Sea. Detailed information are given on the morphology, ecology and distribution of the species recorded for the first time in the studied areas. In addition, an update on the distribution of the genus Prosphaerosyllis San Martín, 1984 in the Mediterranean is given and an identification key is provided.