Once she had acquired her hereditary throne Theodora immediately pursued with vengeance those who had plotted to make the proteuon ruler, depriving them of their property and sending them into exile. She promoted all her eunuchs to high office, appointing Theodore to be domestic of the scholai for the east and sending him to the orient to obstruct the inroads of the Turks (she had previously removed the magister Isaac Komnenos from his position of stratopedarch). Monomachos had already shipped all the Macedonian forces over to the east with Macedonians exclusively in command (of whom Bryennios was one) because it was rumoured among the Turkish people that they would be overturned by a force similar to that with which Alexander the Macedonian overturned the Persians. She appointed Niketas to be logothete of the drome, Manuel droungarios of the watch. She also appointed to her service the synkellos, Leo Strabospondylos, who had served under the emperor Michael, on account of his experience in the administration of public affairs.

When Leo, Archbishop of Bulgaria, died she appointed the monk Theodoulos, originally from Iconium, a city of Tetrapolis, hegoumenos of the monastery of the great and holy martyr Mokios; he was totally ignorant of secular learning but was profoundly versed in divinity, exuding the grace and virtue which sacred studies inspire.