The roots of this controversy date to the time of the last great imperial persecutions of African Christians, and was compounded by the cultural differences between Latin-speaking and non-Latin-speaking believers. At the beginning of the fourth century, during the reign of emperor Diocletian, there was a fierce persecution of Christians aimed at eradicating Christianity and having all Christians participate in the imperial Roman religion in order to help unify the empire. The first of four edicts called for Christians to be outlawed, their churches razed, and their Scriptures given up and burned. In Africa, where persecution was particularly intense, church officials who gave up sacred books became known as traditors (as distinct from traitors, which is a different term). Eventually, this term was applied to those who gave up sacred eucharistic utensils or other believers, or even to those who fled or used any form of subterfuge to avoid persecution.

After Diocletian abdicated in 305, the persecution relaxed. A new controversy developed as Christians reorganized, however. The status of those who had been traditors during the persecution was sometimes called into question, but in 311, it precipitated an open schism. The bishop of Carthage had died, and when a deacon Caecilian was elected in his place, his installation was challenged on the grounds that one of the bishops who had consecrated him had been a traditor (there is evidence that underlying reasons for the schism were also greed, and social and geographical distinctions, but the theological issues are the most important for our purposes). The more rigorous element in the church at that time insisted that sacraments must be performed by blameless individuals, which they insisted traditors were not. They elected their own bishop, Majorinus, and excommunicated Caecilian and his supporters. Majorinus' faction grew, and quickly set up its own parallel clerical structure in opposition to the Catholic church. In fact, as a rule, these rigorists excommunicated not only traditors themselves but also those who had communion with them, and rebaptized all those who joined their ranks from the Catholic church. They became known as Donatists because when Constantine, who was eager to resolve the schism, summoned the church leaders involved to Rome to speak to an ecclesiastical tribunal, their delegation was led by a bishop named Donatus (who may have been Majorinus' successor as bishop of Carthage).

In fact, Donatism was not put down so easily, lasting until after the Muslim invasion in the seventh century. Fueled by ethnic differences and assisted at times by a fanatic religious party called the Circumcellions, the Donatists outnumbered Catholics in parts of North Africa, and most towns had a Donatist as well as a Catholic bishop. By the time Augustine was serving as bishop of Hippo, Donatism presented a major theological and pastoral challenge. In response to the Donatist conviction that valid sacraments depended on the worthiness of the celebrant, Augustine replied that if this were true, all Christians would have to live uncertain about their own baptisms. Augustine's view of God's sovereignty led him to conclude that even dishonourable clergy can still be used by God. Augustine's doctrine of just war also developed in the context of Donatist sentiment, specifically concerning how to righteously subdue the fanatical Circumcellions, who were particularly notorious during Augustine's lifetime. Although his attempt to bring unity to the African church was not completely successful, his theological position was ultimately adopted as the official position of the Western church.