Arguably, the first Christian heretics to be executed
for heresy were Donatists in the fourth century - long before the Middle Ages.
Priscillian is often cited as the first person to be executed for heresy, but although he was a heretic and he was executed, he was actually executed for sorcery.
Priscillian was certainly executed by secular authorities rather than religious ones. In the case of the Donatist martyrs, however, I don't think one can draw such a distinction. The main figures behind the deaths were Paulus and Macarius, commissioners sent by the emperor Constans, so one might blame the secular authorities rather than the ecclesiastical ones - but the emperor Constans was a Christian. It's a mistake to draw a clear distinction between the actions of political rulers and those of ecclesiastical ones, and say that the former are "political" and the latter are "religious", in each case exclusively. A political ruler is perfectly capable of doing something for religious reasons, just as an ecclesiastical leader is quite capable of doing something for political ones.
Domen said:
Theodosius I accepted Christianity as national religion of the Roman Empire because he saw its potential as instrument of exerting political power.
And also because it would increase his popularity among his subjects (most or large part of whom were already converted to Christianity).
What evidence do you have for these claims? Why are they better explanations for Theodosius' actions than the simpler one, which is that he was brought up as a Christian and was a sincere believer?
Personally I'm wary of the common claim that Constantine or his successors endorsed Christianity because they thought it would be an effective tool for exerting political power. The whole history of the fourth century shows that it was exactly the opposite: it was a divisive religion, consisting of a number of squabbling sects, which forced the emperors to devote their precious time and attention to trying to
resolve problems. Far from consolidating power, it diffused it, as the existing political classes were suddenly joined by a whole host of bishops and other ecclesiastics who, given legitimacy by the state, siphoned power away from it. Sometimes that was deliberate, as when Constantine set up the episcopal audience, giving bishops the ability to judge civil cases, thereby freeing up the state legal system to handle more urgent and important matters. But while that was a sensible move, one can hardly say it increased the emperor's power.
I don't think any emperors of the time thought in terms of "national religions" in the first place, either. That's a modern notion. Theodosius never officially made Christianity the religion of the empire, any more than Constantine did. All he did was enact various pieces of legislation that
in effect made it the official religion. And he didn't do it at the Council of Constantinople in 381, either - he did it throughout the 390s, a much later period of his reign.