After the division of the Roman empire into the Western and Eastern empires Cherson (this shortened form replaced the ancient name of the city approximately at the end of the 6th century) became one of the frontier regions of Byzantium. During the entire medieval period it served as the major Byzantine outpost in the northern Black Sea region. The Byzantine administration made every effort to preserve its control over this strategically important point. From here Constantinople witnessed the migrations of nomadic tribes of the steppes and pursued a policy of neutralizing its most dangerous neighbors by instigating conflicts among the tribes. Cherson's role as an economic, commercial, and cultural center of Crimea was ensured because of its interaction with neighboring nomadic peoples. However, the inhabitants of the more central regions of Byzantium always perceived Cherson as a distant provincial town "on the farthest periphery of the Roman world" (Procopius of Caesarea, 6th century), and a place of exile for political and church figures disagreeable to Constantinople. Among those banished to Cherson were Pope Martin I (AD 655), Justinian II (AD 695), caesares Nicephorus and Christophorus (AD 775), and others.

Remoteness from Constantinople resulted in the gradual strengthening of separatist inclinations in Cherson. Until the middle of the 9th century Byzantine officials were forced to share power with representatives of the local body of self-government, which aimed at conducting policy independent of the central government. One of the most exciting pages of the whole history of Cherson involves the struggle for the Byzantine crown between Emperor Justinian II and Bardanus-Philippicus from Cherson, who eventually succeeded to the throne (early 8th century). Cherson's struggle for independence always troubled the central government, which is why in 841 the city was made the center of a theme - a military administrative unit headed by a strategus appointed from Constantinople. This measure did not curb the rebellious spirit of the city, and at the end of 10th century the Chersonites probably joined in a revolt led by Bardas Phocas and Bardas Sclirus, feudal lords in Asia Minor. A corps of six thousand from Kyivan Rus' helped Byzantine emperor Basilius II quash the rebellion in Asia Minor, while Grand Prince Volodymyr suppressed the insurgency in Cherson. In exchange for this assistance the Byzantine emperor gave the princess Anna, daughter of Romanus II, in marriage to Volodymyr. In ancient Rus' chronicles Cherson (Korsun') is named as the location of Grand Prince Volodymyr's baptism.

The ecclesiastical history of Cherson commands a distinct chapter in the life of the city. Hagiographic legends date the beginning of the Christianization of Cherson to the 1st century AD and associate it with the names of Apostle Andrew and Pope Clement. According to the Lives of the Bishops of Cherson, another hagiographic source, the first Christian missionaries came to Cherson from Jerusalem, and the triumph of Christianity in this city was made possible thanks to the assistance provided to Bishop Capitonus by Constantine the Great, who sent him an attachment of ballistarii. However, archaeological and epigraphic sources allow for the correction of this legend. The earliest Christian sites of Cherson date to the second half of the 4th century and give evidence for the advent of Christianity to this city from Asia Minor, not from Palestine. The military garrison, which is mentioned in the Lives, was installed in the city under Valentus, that is, after Constantine's reign. Moreover, Valentus sent this garrison to secure the safety of Cherson upon commencing war with the Goths, and not to introduce Christianity by force. Also, according to the Lives, the bishop Aetherius was a contemporary of Diocletian, but in fact he is recorded as signing the acts of the Second Ecumenical Council which took place in Constantinople in 381. The author of the Lives, himself probably a bishop of Cherson, attempted to underscore the high position of the local church within the ecclesiastical hierarchy and to connect the history of the city with the most outstanding and prestigious events of the history of Byzantium. Thus he attributed the formation of the bishopric of Cherson to the bishop of Jerusalem and introduced Constantine the Great, the founder of the Christian empire, into the history of Cherson.

Constantine the Philosopher (Cyril), one of the authors of the Slavonic alphabet, traveled to Cherson in 860-861 and stayed there for almost a year. He found the relics of St. Clement of Rome who had been exiled to Cherson at the end of the 1st century AD and had died at the hands of the pagan inhabitants. It is possible to trace the route taken by Constantine as he carried the relics of St. Clement back to Rome. Relying on archaeological evidence from excavations in Chersonesos, which have been under way for 160 years, one can estimate the locations of the churches mentioned in Constantine the Philosopher's tract "On the transmission of the relics of St. Clement." Later, some of the relics were given to the pope in Rome where they are preserved today in the Basilica of St. Clement. The remainder of the relics was kept in Cherson for more than 100 years. In 989 Grand Prince Volodymyr transported them to Kyiv and deposited them in a chapel of the Desyatynna (Tithe) church, where they were probably destroyed along with the church during the siege of Kyiv by Khan Batiy.

The Mongol-Tatars began their continuous devastating raids on Crimea in 1223. Cherson was initially destroyed in the third quarter of the 13th century, possibly by Khan Nogay in 1278. The city never again recovered its previous scale and its borders were limited to the port district. In addition, the installation on the southern Crimean coast of Italian colonies, which soon became centers of Venetian and Genoese commerce, and the transfer of principle trade routes to the eastern coast of Crimea spelled the end of Cherson. Thus ended the city's role as a center of commerce. Documents of the patriarchy of Constantinople describe the abject poverty of the bishopric of Cherson and are written evidence for its desperate state at this time. For example, in the first half of the 14th century (1318-1347) the patriarch of Constantinople requested a pledge from Metropolitan Jeremiah that he would not stay in Constantinople and would not ask to be assigned to an alternative place (Cherson received the rank of metropolitanate in 1280.) At the end of the 14th century the metropolitan of Cherson, suffering heavy privations, took parishes in the neighboring bishoprics of Gothia and Sugdaia.

In 1399 the Tatars finally destroyed Cherson, so that only ruins remained where once stood a prosperous city. The last metropolitan of Cherson was appointed in 1440 and lived in the outskirts of town. However, the ruins of Cherson were not left in peace. Initially the Genoese were afraid that the Turks would use the ruins for military purposes and thus demolished the remains of the defensive walls. Later, the Turks dismantled and carried away a great number of marble architectural details. Fortunately, the city was never rebuilt again, and so the upper layers of the site were left intact. The patterns of conflagration and devastation provide material for the study of the life of a late Byzantine city.