The timing of the Holocene transition of the Black Sea from a brackish lake to a marine sea has long been debated. Here, we report on the earliest records of cetaceans in the Black Sea region as a proxy for the connection with the Mediterranean and the transition from a brackish to marine environment. We base our analysis on cetacean skeletal finds and archival data on cetacean skeletal remains from the Bosphorus, the western, northern and eastern Black Sea, and the Kerch Strait. We find that all three contemporary cetacean species in the Black Sea – the harbour porpoise, bottlenose dolphin and common dolphin – had migrated out of the Mediterranean to the Bosphorus and the Black Sea at least 8000–7000 years ago and reached the northern Black Sea by 5500 years ago at the latest. Our study suggests the establishment of a Mediterranean–Black Sea biogeographical connection for marine vertebrates at least 7000 years ago. The early presence of cetaceans in the Black Sea has implications for understanding its Holocene transition, as well as the evolutionary and ecological history of these species more generally.