The Greek colony of Dioscurias (or Dioskurias) was founded here in the mid-6th century BC. From the time of Pliny (N.H. 6.14-16) and Arrian (Periplus ponti euxini 10.3) it was known as Sebastopolis; Aidan Liddle, in his translation of Arrian's Periplus, notes that the towers of Dioscurias have been found beneath the surface of the Black Sea, and speculates that the encroaching sea forced the inhabitants to relocate to Sebastopolis. It was the Turkish fortress of Suhum-Kale when Russia occupied it in 1810.

An earlier settlement of the second and early first millennia BC, frequented by local Colchian tribes, was replaced by the Milesian Greek colony of Dioscurias (Greek: Διοσκουριός), geographically the remotest that Miletus ever established. The city is said to have been so named for the Dioscuri, the twins Castor and Pollux of classical mythology. It became busily engaged in the commerce between Greece and the indigenous tribes, importing wares from many parts of Greece, and exporting local salt and Caucasian timber, linen, and hemp. It was also a prime center of slave trade in Colchis. The city and its surroundings were remarkable for the multitude of languages spoken in its bazaars.

Although the sea made serious inroads upon the territory of Dioscurias, it continued to flourish until its conquest by Mithridates VI Eupator of Pontus in the later second century BC. Under the Roman emperor Augustus (known in Greek as Sebastos) the city assumed the name of Sebastopolis. But its prosperity was past, and in the first century AD Pliny the Elder described the place as virtually deserted though the town still continued to exist during the times of Arrian in the 130s.[4] The remains of towers and walls of Sebastopolis have been found underwater; on land the lowest levels so far reached by archaeologists are of the first and second centuries AD. In 542 the Romans evacuated the town and demolished its citadel to prevent it from being captured by Sassanid Iran. In 565, however, the emperor Justinian I restored the fort and Sebastopolis continued to remain one of the Byzantine strongholds in Colchis until being sacked by the Arab conqueror Marwan II in 736.