Legend relates how a disciple of Jesus Christ, one Bonifatius, preached the Gospel in Cagliari in the 1st century. There were probably bishops at Cagliari from an early date, however, as Athanasius of Alexandria speaks of previous episcopal martyrs (during the Diocletian persecution most likely) in a letter to his contemporary, the first well-known bishop of Cagliari, Lucifer. Cagliari remained Roman Catholic despite the Arianism prevalent at the time and many African bishops fled the Arian Vandals to come to Cagliari. At the time of the Second Council of Constantinople (681), Cagliari was already a metropolitan see. It has been suggested that in the 10th and 11th century as the giudicati of Sardinia became independent, the archbishop of Cagliari became the de facto theocratic ruler of the island through the Corona de Logu.
In 1075, Pope Gregory VII reproached the Archbishop James for wearing a beard, a fashion which had been introduced into Sardinia at an earlier date; the pope asked the Judge Torchitorio I to oblige the clergy to abandon this custom. The same bishop and his colleagues were blamed by Pope Victor III (1087) for neglect of their churches. Under this pope, the Archbishop of Cagliari became known as the Primate of Sardinia. In the 12th century, however, the prominence of Cagliari was reduced vis-à-vis the Archdiocese of Torres in the north of the island. In 1158, the title of Primate of Sardinia and Corsica was given to the Archbishop of Pisa, but in 1409 it was reassumed by the Archbishop of Cagliari, whence arose a controversy between those sees, which dragged on into the 20th century.