Another claimant:
Greek colonisation and possibly also
Phoenicia (what's now Lebanon) over the 8th - 6th centuries BCE.
Greek colonizers spread to the shores of the Black Sea, the E Aegean Sea (W Turkey), S Turkey, N Cyprus, N Egypt, NE Libya, E Spain, S France, S Italy, and E Adriatic. Marseille, France (Massalia), Nice, France (Nicaea), Palermo, Sicily, Italy (Panormos), Naples, Italy (Neapolis), Split, Croatia (Asphalatos), and Benghazi, Libya (Euesperides) were originally Greek colonies.
The biggest Phoenician colony was Carthage, near present-day Tunis.
Let's now turn to Ukrainian Black-Sea cities.
Odessa was earlier named Khazhibei, but in 1795, some Russian renamed it after the Black Sea Greek colony of Odessus, because that Russian mistakenly believed it to be there. Odessus is, instead, Varna, Bulgaria.
The Ukrainian spelling of its name is "Odesa", with only one s.
Sevastopol was founded in the late 18th cy. under the name Akhtiar, but it was soon renamed with a Greek-style name: sebastos "venerable" + polis "city".