In the period before Constantine converted to Christianity, the pagan Romans at various points had persecuted certain groups of Christians who were unwilling to participate in the state religion. Some emperors, such as Trajan (as we see in his correspondence with Pliny) did so in a reluctant and limited manner, but others, such as Nero and Diocletian, concerned to some degree that the Christians had angered the gods, persecuted them more aggressively.
After Christianity became the religion of the Roman Empire, gradually the positions were reversed, with increasing persecution of both pagans and heretics by the Christians. The essential rationale was quite different. Although the pagans had no objection to Christians worshipping one more god in addition to the state gods, their objections were centered on bringing down the wrath of other gods by exclusive worship. In the case of Christian repression of paganism and heresy, the issue was that only one God could be worshipped in one way.
In the resolution of the Donatist heresy, Augustine, Bishop of Hippo, established not only the theory of just war, but also the precedent that the Roman army could be used to exterminate Christian heresies (and heretics).