После коронования Иоанна Дуки по всей Византии начались беспорядки; они продолжались около двадцати лет, временами принимая характер настоящей гражданской войны. Малик-шах, унаследовавший трон Великих Сельджуков, наблюдал за этими событиями со вниманием, отмечая, что искусность Сулеймана в дипломатии не уступает его умениям в военной сфере. Примерно в 1077/78 году Малик-шах убедился, что Сулеймана можно назначить правителем Рума. Вполне возможно, что это назначение помогло Михаилу, по-прежнему находившемуся в шоке от предательства союзника-норманна, принять решение последовать примеру создавшего опасный прецедент Русселя и в свою очередь обратиться к Сулейману за помощью в борьбе против мятежников. Прежде чем послать ответ, Сулейман посоветовался со своим сюзереном Малик-шахом. Султан не заставил себя ждать с ответом, ведь он тоже очень хорошо понимал, что можно получить от такого сотрудничества.

Таким образом, Сулейман смог вступить на территорию собственно Византийской империи как добрый союзник ее правителя. В Византию, которую страстно желал покорить, он вошел во главе весьма многочисленного войска. Сельджуку везло: вскоре он смог захватить Русселя, однако, нарушая обещание, он отказывался доставить его императору до тех пор, пока тот не заплатил за норманна солидный выкуп. Получив Русселя, византийцы недолго продержали его в пленниках: дело в том, что одновременное появление в 1078 году еще двух претендентов на трон вынудило императора объединить вокруг себя всех способных оказать ему помощь союзников. Руссель был выпущен на свободу в обмен на обещание защищать законного императора.

Два претендента, почти одновременно заявивших о своих претензиях на трон, появились в разных частях империи. Один, Никифор Вотаниат, пришел с запада. Добравшись до Адрианополя, он объявил себя императором, после чего продолжил поход на Константинополь. Другой мятежник, Никифор Вриенний, действовал в Малой Азии, где вербовал в свою армию беженцев-греков из Манцикерта.