In the turbulent period after the Battle of Manzikert in 1071, when several generals tried to seize the throne for themselves, Melissenos remained loyal to Michael VII Doukas and was exiled by his successor Nikephoros III Botaneiates.

The campaign ended in defeat near Sebasteia (modern Sivas), and Melissenos along with Manuel Komnenos were captured by a Turkish chieftain whom the Byzantines called Chrysoskoulos.

[9][13] In reply, the Komnenoi offered 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 would submit to them.

[14][15] At the same time, Nikephoros Botaneiates tried to forestall the capital's fall to the Komnenoi by sending for Melissenos and asking him to enter the city and assume imperial authority.

[16][17][18] This act of submission, unique among the various rebels of the time, may throw some light on Melissenos's motivation for his uprising, according to the historian Jean-Claude Cheynet.

Thus, by becoming involved in the Byzantine civil wars as mercenaries and allies – especially through their use by Botaneiates and Melissenos during their respective revolts to hold down various cities for them – the Turks completed their relatively peaceful take-over of central and western Asia Minor.

[16][23][24] In the 1083 campaign in Thessaly against the Normans, who, under Guiscard's son Bohemond were besieging Larissa, Melissenos was used by Alexios as the centerpiece to a ruse de guerre.

[25] Melissenos fought alongside Alexios in the Battle of Dristra in late August 1087 against the Pechenegs, commanding the Byzantine left wing.

Occupied with this task, he did not join the imperial army in time for the crushing Byzantine victory over the Pechenegs at the Battle of Levounion on 29 April, arriving the next day.

[27] Later in the same year, he participated in the family council of Philippopolis which examined the accusations of conspiracy raised against John Komnenos, the doux of Dyrrhachium by the Archbishop of Ochrid Theophylact.

The council degenerated into a heated family quarrel, where John's father, the sebastokrator Isaac, accused Melissenos and Adrian Komnenos of slandering his son, but in the end Alexios dismissed the charges.