Еще более губительные неудачи ждали ромеев на другом конце Империи, на Востоке. Здесь в 40-е гг. XI в. появились новые воинственные враги, исламизированные племена великолепных конных лучников, туркмен-сельчуков, или сельджуков, как их называли арабы, которые к тому времени уничтожили остатки арабского господства в Средней Азии, в 1055 г. овладели Багдадом — некогда блестящей столицей халифата Аббасидов и от имени Багдадского халифа стали номинально править Ираном, Ираком и северной Сирией. Халиф объявил их вождя, Тогрул-бека, внука Сельчука, обратившегося в ислам суннитского толка, «
Поначалу сунниты-сельчуки не ставили своей целью захват собственно византийских территорий. Их основной удар был нацелен против ненавистных султанов-шиитов из династии Фатимидов, чье государство раскинулось от атлантического побережья Марокко до Сирии и Аравии. Тем не менее, именно с сельчуков-сельджуков началась турецкая экспансия — медленно развивающаяся, но смертельно опасная болезнь Ромейского царства, поразившая сначала степные плоскогорья, а затем добравшаяся до южного побережья Малой Азии. «Как голодные волки», — по выражению армянского историка, — сельчуки накинулись на такие цветущие ромейские города как Милитина, Феодосиополь в Армении, Кесария — столица Каппадокии, Колоссы во Фригии, на юго-западе полуострова. Только при взятии древнего Феодосиополя — армянского Арзана погибло до 150 тысяч жителей, а чтобы вывезти захваченные в городе сокровища победителям понадобилось 10 тысяч телег. Все к северу от Кесарии Каппадокийской было занято сельчуками, безжалостно разграблено или превращено в выжженную пустыню. Правда, враги встречали сопротивление партизан-акритов, уничтожавших отдельные разбойничающие отряды и в свою очередь нападавших на туркменов, но вообще восточная Анатолия оставалась беззащитной перед опустошительными набегами, поскольку организованной системы обороны, линейной защиты границы давно не было, как не было и средств для ее создания. Крах оборонительных структур, пренебрежение к оборонительным мероприятиям принесли свои зловещие плоды. Старые ромейские фемы были демилатиризованы и упадочны. Неповоротливые, разношерстные, пестрые имперские войска никак не могли справиться с ситуацией, становившейся невыносимой. Лишь благодаря флоту за Империей сохранились некоторые береговые области Малой Азии и Сирии.
Крупное поражение от туркмен, славившихся своей отчаянной храбростью, маневренностью и военной опытностью, ромеи потерпели все в том же роковом 1071 г. в битве недалеко от кастрона