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

А в Константинополе в 1081 году на трон взошел новый император Алексей. Что касается азиатской части империи, то там он столкнулся с такой ситуацией, на урегулирование которой не мог рассчитывать до тех пор, пока не восстановит порядок в своей столице и в западных регионах страны. Несмотря на то что решение этой задачи заняло пять лет, уже к 1083 году он был готов обратить свой взор на восток. Намереваясь вернуть утраченные земли в Азии, он пересек Мраморное море и пошел войной на Сулеймана. Сельджук отступил, по обычаю кочевников сжигая за собой зерно. Опасаясь голода в том случае, если он продвинется слишком далеко, Алексей размышлял, что делать дальше – атаковать Иконий (Конью) или Филомелию (Акшехир). По утверждению его дочери, он решил эту проблему следующим образом: написав на листках бумаги названия обоих городов, провел ночь в молитвах; наутро на заре «в присутствии всех» священник выбрал одну из сложенных бумажек и прочел название города – это была Филомелия. Император привел войско к Филомелии и вынудил противника выйти на бой. Борьба Сулеймана с византийцем была долгой. В ее ходе погиб сын императора Андроник Порфирогенет, однако Сулейману все же пришлось сдать византийцам Никомедию, а на последовавших за этим переговорах султан был вынужден согласиться на одну из форм вассальной зависимости. Правда, и император должен был отдать некоторые территории сельджукам, хотя и представил дело так, будто уступил их султану на правах колонии.