Trichodina zaikai sp. n. is described from the gills of Crenilabrus ocellatus, C. griseus and Hippocampus hippocampus microcoronatus from the Black Sea, and from C. griseus from the Mediterranean. Seven species of trichodinids, Trichodina jadranica Haider, T. lepsii Lom, T. ovonucleata Raabe, T. partidisci Lom, T. rectuncinata Raabe, Trichodina sp. 1 and Paratrichodina obliqua Lom are reported for the first time from the gills of fishes from the Bulgarian Black Sea coast. Three species, T. ovonucleata, T. rectuncinata and Trichodina sp. 2 are reported from the French Mediterranean coast. All species are characterized by photomicrographs and morphometric data. One of the most common trichodinid species occurring on the gills of marine coastal fish, T. rectuncinata, exhibits an unusually great range of morphological and size variation in population from different hosts. This variation is recorded in detail and discussed.