Isaac remained in exile for six years, during which time he traversed most of Asia Minor and the Levant, seeking to create a broad alliance with other rulers, both Christian and Muslim, against his brother. The main sources for this period of his life are Choniates, the court poet Theodore Prodromos, and Michael the Syrian. From Melitene, Isaac went to Trebizond, whose governor, Constantine Gabras, had broken away from Byzantium in 1126 and was ruling the area of Chaldia as an independent prince. In the winter of 1130–1131, according to Michael the Syrian, Isaac met again with Gabras, and a league was created between Isaac, Ghazi and the Sultan of Rum, Mesud I (). Isaac then went to Armenian Cilicia to entice its lord, Leo I, into the league. He was initially well received in Cilicia and spent some time there. His eldest son John even married one of Leo's daughters, and received the cities of Mopsuestia and Adana as her dowry. After a short while, however, they fell out with Leo too, and were forced to seek shelter with Sultan Mesud, abandoning their possessions in Cilicia.