Melissenos is encamped in March 1081 with his army at Damalis, on the Asian shore across the Bosporus from Constantinople, when he receives news of the revolt of the Komnenoi against Botaneiates and the proclamation of Alexios Komnenos as emperor.

He sends letters to the Komnenoi, suggesting a division of authority over the imperial territory, with the Balkans remaining under Komnenian control and himself keeping Asia Minor, although he also emphasized that the Byzantine Empire should remain united.

In reply, the Komnenoi offer to recognize him as Caesar—the second highest dignity after the imperial title itself—and to give him the governance of Thessalonica—the Empire's second-most important city—if he will submit to them.

Melissenos initially refuses to accept this offer, but as the Komnenoi are on the verge of taking Constantinople and might refuse to make similar concessions later, he eventually agrees.

At the same time, the emperor Nikephoros Botaneiates tries to forestall the capital's fall to the Komnenoi by sending for Melissenos and asking him to enter the city and assume imperial authority.

His envoys, however, are obstructed by George Palaiologos and never reach Melissenos.