In the early Middle Ages, the city appears to have been under very loose Byzantine control, like other cities in the region. Archaeological remains indicate considerable construction activity near the shore in the 6th century. Under Byzantine influence, the city was subject to Christianization, and became the seat of a bishopric under the Patriarch of Constantinople, attested for the first time in the Second Council of Nicaea in 787. Bishop Stephen, who attended the council, was an iconophile persecuted by Emperor Constantine V. He was later canonized (St. Stephen of Surozh; ), and buried at the Hagia Sophia cathedral in Sougdaia, which according to later tradition was built in 793. Although a Greek-speaking population was probably settled in the city, the area remained dominated by the Alans: a 9th-century hagiography of Apostle Andrew places "Upper Sougdaia" elsewhere, between Zichia and the Cimmerian Bosporus, "in the land of the Alans", while the hagiographer of Constantine the Philosopher mentions the tribe of "Sougdoi", situated between the Iberians and the Crimean Goths, which the historian Francis Dvornik identifies as the Alans.