With new leadership, the nature of the war changed with a wholly new strategy. The Cypriots were the greatest naval power in the Empire, and they used the navy well. In a tense battle off Crete, the Elegemitoi scattered the fleet of the Katakaloi, the most distinguished naval force on Ekaterina’s side, and prevented Crete from sending reinforcements throughout the war. They also severely defeated the Monomach fleet at the approaches to Tripoli, leaving Syria and Thrace isolated from each other, unable to deliver reinforcements, and, more importantly, food and supplies. Their plan would be to hold the Monomachs in Greece, and defeat them in Syria. This was a very good plan. Ekaterina’s early campaign, although it made deep inroads beyond Thrace and into Macedonia, wasted a lot of men, and when the exceptionally hot summer came, plague and thirst wasted the Monomach army. The new Emperors held Ekaterina at Thessaloniki, then pushed back to Nikopolis, then stopped pursuing, knowing that her forces were in no shape to attack them again. At the same time, Elegemites armies from Greece under Theodore himself landed in Syria, and pushed Ekaterine’s forces (much-reduced as men were transferred to fight in Europe the previous year) back, until they besieged the great coastal city itself. After a tough, four-month siege the fortress was stormed and the slaughter was terrible; it was also then that the legitimate wife of Heraklios and her children died, in the confusion and the chaos. For Ekaterine, that proved an unexpected support.
Her followers were seeing things go badly; her spies reported grumbling. All her sins, her indiscretions, her ambitions - were clear signs that she would fail. She decided to go on the grandest show of penitence in royal history, walking barefoot from church to church in Constantinople, and donating vast riches to monasteries, even if she needed to pay her troops. Then, leaving most of her army within the walls of the city, she headed back to Kiev. Her relief force scored a stunning victory over the unprepared Knytling army, and once again they retreated. Kiev and Pereyaslavl, eager to avoid repercussions, welcomed Ekaterine once again. Once in control of the Russian heartland, she did what she did in Constantinople, but on a grander scale, visiting every city between Chernigov and Pereyaslavl on an ambitious penitent journey, bewailing the sins of her youth, and the fate of her son - the only remaining heir of Herakliy Nikiforovich, her husband to whom they were joined in secret. A priest was found to confirm the story, of course. That last message stuck; as the Russian people forgave her, they also acknowledged her son. Talk arose in Kiev of making Fedor the next Emperor. Over the winter, more troops were levied and hired, and Ekaterine’s war effort resumed. The situation in Greece was a stalemate. The Elegemitoi couldn’t take Constantinople, the Monomachs couldn’t take Thessalonki. Tmutarakan was then chosen as the next target. A small part of the Monomach army was directed south, to support Constantinople. Another sailed down the Dniepr and landed at several Knytling-held fortresses, trying to draw the opponent south. The last and biggest marched east and quickly took both Novgorod and Ryazan and then struck south along the Don. The Knytlings retreated purposefully, gathering numbers, and finally faced the army at Bela Vezha. The battle was very bloody, and although Ekaterine’s levies suffered much higher losses than the experienced though demoralized professionals of Dimitri, Tmutarakan’s forces were much reduced, to the point where they couldn’t defend anything outside their own city. Still, Ekaterine needed her troops intact, and she also needed to move faster than the new Emperor Ioannes. She met with the Knytling prince and proposed a treaty Dimitri couldn’t refuse; she would cede Crimea to him, while he would return her Severia, and Cumania would go to Itlar Dimitrievich. The Knytlings could remain allied to the Elegemitoi, but there were to be no more hostilities between Kiev and Tmutarakan.
The victorious army sailed over the Pontus to Trapezund, marching through friendly territory to Syria, but was unable to make much progress beyond Aleppo; the Elegemitoi had sufficient numbers to stop them, and naval dominance to keep it that way. The army in Constantinople marched to Thessaloniki, only to be handed a heavy defeat by the larger Elegemites force. Another approach had to be attempted. The weak point in the Elegemitoi plans was Bulgaria. Splitting the forces from Constantinople, the Monomach army struck through Wallachia and Bulgaria towards Vidin, another Imperial city whose loyalty tended towards the Monomachs. The operation caught the Emperor by surprise and its success was total. The Elegemitoi were forced to react and leave their defensive positions, chasing the Monomach army which pushed ahead into Croatia, still allied with the Emperor. Croatian soldiers formed a large part of the garrison in Thessaloniki, and the small country found itself barely defended. After the fall of two border fortresses, the Croatians signed peace. After almost three years of war, the opponents were now somewhat evenly matched, but to Ekaterine it looked like might still win. The Elegemitoi were now losing support as rapidly as they had taken it from the hapless Andronikos, their allies had deserted them, and everywhere except in Syria she was gaining ground. At the same time, she could not raise as many troops as her opponents, and they had to be collected from a much larger area.
As summer rolled into autumn, the elder of the Elegemitoi brothers, at the head of an army sent in pursuit of the Monomachs in Western Macedonia was caught in an ambush and killed. The younger brother was quickly acclaimed sole Emperor by his supporters. He was the one truly brilliant general of this war, though also by far the most bloodthirsty. After a long and elaborate diversion, he lead Ekaterina’s commanders to think that he was trying to sail with his forces to Syria to finish off the job. Her spy network, for once, didn’t have enough solid information to provide her with, and she gave the go-ahead to an advance on now-weakened Thessaloniki. However, the Elegemites navy instead attacked Constantinople itself, breaking through the seaward defenses under cover of night. The Monomach garrison panicked, and everyone of importance, including Ekaterine, fled the city. It was a remarkable failure on the part of Monomach intelligence and army, of course, and a remarkable success on the part of the Elegemitoi. Theodore’s troops then sacked the capital, committing bloodshed indiscriminately, ending any hope of a pro-Monomach popular uprising. Reinforcements sailed in through the harbour daily. Ekaterine watched in powerless fury. With dedicated defenders inside the walls, Constantinople was far too much to handle for her. Peace was signed at last, with both Theodore and Ekaterina knowing that the war would have to be continued in other ways. Bulgaria and Russia were made Monomach possessions. Theodore was to remain Emperor. Ekaterine was to surrender Aleppo and Alexandretta. This was 1228.
The Emperor and Ekaterine exchanged several assassination attempts over the next few years, with one of them nearly ending the life of Ekaterine’s son Fedor. However, Ekaterine’s agents in the end proved more successful. The Elegemitoi ambitions were thwarted, and young prince Manuel in Cyprus was not up to the task of replacing his uncle as Emperor. The nobles of the Empire chose another man, of the venerable Russian dynasty that took Nikomedia around the same time that the Rurikids took Constantinople but Hellenised thoroughly. Although elderly, Konstantine Nikomedikos unexpectedly proved a worthy political opponent, keeping Ekaterina’s ambitions at bay, and weakening her power-base by granting the Tsardom of Bulgaria to the Chervens of Varna, and reconciling with the Trapezuntine Ariminikoi. This strengthened the Emperor's position and undermined Fedor’s already-shaky legitimacy; Fedor even lost Vidin to the Cherven Tzar as a result. His mother was highly disappointed in him, of course. He was proving to be an unworthy successor, but he was her son. Still, she had to make sure the legacy continued in case he died. Her Kievan voivoda, Sviatoslav Gavras, fought a quick war in 1231 to annex boyar Volhynia, and with help from Alexander Philanthropenos of Lithuania placed Arsenios Nikiforovich to the throne. In case Fedor’s line were to die out, Arsenios would inherit the vast Monomach lands. In 1333, after having eluded the blades of Ekaterine’s best assassins for two years, Konstantine Nikomedikos died of old age, childless, naming Andrew Knytling, the son of Daniel of Tmutarakan as successor. He was the Empire’s second chance, a charismatic man who managed to endear himself to the Greeks through diplomatic skill and adopting the Greek manners wholesale. Ekaterine knew the young man well, and despite the recent civil war, the two Rurikovich branches reconciled and relations were warm. She met with him and convinced him to accept her back as a subject of the Empire. This was a tremendously important move, of course. It would have returned him half the Empire and his prestige would rise if he accepted; at the same time this assured Monomach return to the throne within a generation or two. However, Knytling fortunes were far from secure, Tmutarakan having proved very vulnerable during the Civil War and the Greek nobles still divided over having any non-Greek Emperor. She remedied that by promising his nephew the throne of Syria – in its entirety. Andrew agreed, and they signed the accord in Tripoli in 1334. Ekaterine died shortly thereafter – not quite defeated still, because her descendants now had a good chance to inherit the throne – and keep it, if they proved strong enough.