Roman and Early Byzantine era
Along with the rest of Colchis, Abkhazia was conquered by Mithridates VI Eupator of Pontus between c. 110 and 63 BC, and then taken by the Roman commander Pompey. With the downfall of the Roman Empire, the tribes living in the region gained some independence, nominating their rulers who were to be confirmed by Rome. In the 3rd century AD, the Lazi tribe came to dominate most of Colchis, establishing the kingdom of Lazica, locally known as Egrisi. According to Procopius, the Abasgi chieftains were also subdued by the Lazic kings.
Colchis was a scene of the protracted rivalry between the Eastern Roman/Byzantine and Sassanid empires, culminating in the well-known Lazic War from 542 to 562. The war resulted in the decline of Lazica, and the Abasgi in their dense forests won a degree of autonomy under the Byzantine authority. During this era the Byzantines built Sebastopolis in the region. Their land, known to the Byzantines as Abasgia, was a prime source of eunuchs for the empire. The people remained pagan until a mission sent by the emperor Justinian I (527-565) converted the people to Christianity, though at the 325 Council of Nicaea a bishop had attended from the port city of Pityus. Byzantines constructed defensive fortifications that may have partially survived to this day as Kelasuri Wall.