Christianity wasn’t legal until around the time that the Roman Emperor transferred the Capitol of the Roman Empire to Byzantium so it would have to have been later than that.
Why would the Church would hand over the authority to appoint a Patriarch to the Roman/Byzantine Emperor in the first place? I don’t think that the Church ever did do that, do you?
Historically, in the early church the local synods appointed their own bishops and Metropolitans. The bishop of Rome, elected by his own synod, was not generally involved in episcopal appointments except as Metropolitan in central Italy.
Thus, such great luminaries as Saint Ignatius of Antioch, Saint Ambrose of Milan, Saint Irenaeus of Lyons, Saint Vincent of Lerins and Saint Augustine of Hippo were elected by the local synods of those places. This system lasted for several centuries.
Later, when pagan kings converted to Christianity, they (as first citizens and father of their countries
) tended to use their influence one way or another (one might call it bullying) to get bishops appointed whom they liked, or could work with. It isn’t clear how exactly this process developed in each area, but generally in Christian/Catholic countries the kings did start to plant their own men in church offices and this gave them and their successors effective control. So yes, Roman emperors did name Patriarchs of Constantinople but I don’t know when we can say it began.
Charlemagne and his successors controlled the appointments of bishops in his realm, which at the time was the lion’s share and core of western Christendom (considering the Moors had reached the Pyrenees and had taken Sicily too, while the North lands were still pagan in attack mode).
This phenomena of royal appointments happened to the Papacy as well.
The Roman emperors, either from Constantinople or Ravenna, appointed some Popes (which partly explains the “ten Greek Popes”), the Holy Roman emperors did the same in a later era, and there was a period when an interesting character named Theophylact controlled the appointments. During periods in between sometimes the great families of Italy contested for the Papacy.
This was just one of those ‘crosses’ the church had to bear.
