Two spionid polychaetes, Polydora cornuta and Streblospio gynobranchiata, were identified in benthic samples collected in the northern Black Sea and adjacent waters. These species have earlier been classified as the worst invaders in soft bottom communities in the Mediterranean Sea. Polydora cornuta had been previously misidentified and widely reported from the Black Sea and the Sea of Azov as P. ciliata, P. ciliata limicola and P. limicola. Streblospio gynobranchiata is a new invader currently extending its distribution into the Mediterranean, Black and Caspian Seas. Morphology, diagnostic characters and biology of the species are discussed and the history of their records in the Mediterranean, Black and Caspian Seas and the Sea of Azov is reviewed.