Его кампания не пользовалась большой поддержкой, а войско было таким маленьким, что он тоже решил обратиться за помощью к Сулейману! Согласившись помочь еще одному христианину, сельджук с удовольствием внес неразбериху в и так уже запутанную ситуацию. Получилось, что объединенные войска мятежников-греков и вступивших на территорию империи сельджуков продвигались по ней вместе. Сначала они взяли Кизик, а потом Никею, где претендент на трон был провозглашен императором. Затем, продолжая идти бок о бок, обе армии вошли в Никомедию. Оттуда они двинулись в направлении Халкедона с тем, чтобы из Халкедона добраться до Хризополя (ныне Кадикой) – города, расположенного на азиатском побережье Мраморного моря. Там они разошлись; в то время как греческий военачальник морским путем отправился в Константинополь, где намеревался сместить императора и стать полновластным владыкой, сельджук расположился на азиатском побережье, откуда за сверкающей морской гладью он видел город – сердце христианского мира, воплощение имперской мощи.

Приход к власти в 1078 году Никифора Вриенния спровоцировал начало нового восстания греков Малой Азии. Его возглавил генерал Никифор Мелиссен, который по сложившемуся к тому времени у мятежников-христиан этого региона обычаю тоже обратился за помощью к Сулейману. И вновь сельджуки ее оказали, и вновь плечом к плечу войска христиан и мусульман вошли в Вифинию. Византийские гарнизоны этой области, в значительной степени состоявшие из турецких наемников, сдались сельджукам, ведь турки считали их родственниками по крови. В результате численность войска Мелиссена уменьшилась настолько сильно, что он был вынужден отказаться от мысли идти на Константинополь. Вместо этого он решил обосноваться в Вифинии и попросил своего союзника вывести войска с его территории. Однако на этот раз Сулейман не согласился выполнить просьбу грека, а генерал был не в состоянии настоять на своем, поэтому Сулейман имел возможность воспользоваться ситуацией и захватить Лидию и Ионию. Он основал там первый эмират Сельджукидов на земле Анатолии. В 1078 году он провозгласил Никею столицей, а себе взял титул султана.