Между тем кочевые шайки турок с целью грабежа постоянно врывались на территорию Византии в Анатолии, и императорские войска практически не могли задержать их. Турки начали называть себя гази («борцами за веру»). Султан Сельджукид Альп Арслан (Храбрый Лев), племянник и наследник Тугрил Бека, захватив несколько пограничных греческих крепостей, еще более облегчил кочевым ватагам проникновение на имперскую анатолийскую территорию.
Отколовшиеся от Больших сельджуков Альп Арслана Малые сельджуки, или рум-сельджуки (Румом — от слова «Рим» — называлась Анатолия), расположившиеся на востоке Анатолийского полуострова, совершали постоянные нападения на Византию. Другим большим турецким племенем, занявшим северо-восток Анатолии, были данишмендиды.
Греки не могли смириться с турецким нашествием. Однако в 1071 г. одна из попыток императора Романа Диогена разгромить и отбросить турок закончилась страшным поражением огромной греческой армии при Манцикерте в Армении. Пленный император был брошен к ногам сидевшего на коне Альп Арслана. И хотя султан проявил чрезвычайное великодушие, ограничившись данью, изменением границ и обещанием покорности со стороны империи, Византия не скоро смогла оправиться от этого поражения. Турки потоком хлынули на анатолийское плоскогорье. Греческое население бежало в города на побережье и в Константинополь. Захват турками Анатолии облегчался борьбой за императорский трон нескольких соперников и последовавшей чехардой императоров. Чтобы усилить армии для своих междоусобиц, соперники выводили греческие гарнизоны из городов Анатолии и вводили в них нанятые турецкие отряды, которые затем, привыкнув к сытой и благоустроенной жизни городских хозяев, естественно, не хотели из них уходить. Империя потеряла земли, откуда она получала своих лучших солдат и полководцев. Турки принялись также захватывать фатимидские, греческие и армянские владения в Сирии и Месопотамии. В 1071 г. сельджуки захватили у Фатимидов Алеппо (Халеб), в 1073-м в первый раз овладели Иерусалимом и в 1075-м — Дамаском. В 1076 г. Фатимиды отбили Иерусалим, но в 1078-м город был вторично захвачен турками и туркменами, и если с тамошними христианами обошлись более или менее снисходительно, то вся ненависть завоевателей вылилась на арабов-шиитов.
В 1072 г., после смерти Альп Арслана, его наследником стал его несовершеннолетний сын Малик Шах (малик — молодой властитель, принц), сохранивший и расширивший государство, простиравшееся теперь от Средиземного моря до Гиндукуша. Племянник Альп Арслана Сулейман, предводитель рум-сельджуков, в 1080 г. провозгласил себя султаном и начал в непрочном союзе с Византией войну с Малик Шахом. В 1085 г. Сулейман захватил византийскую Антиохию. В 1086 г. Тутуш, брат Малик Шаха, во главе армии Больших сельджуков победил и убил султана Сулеймана и выгнал рум-сельджуков из северной Сирии.
Однако после смерти в 1092 г. султана Малик Шаха государство Больших сельджуков распалось. Его старший сын и наследник Баркиярок не смог удержать его в руках. Он вынужден был, проиграв войну, Ирак отдать своему брату Мухаммеду, а Хорасан (северный Иран) — другому брату, Санджару. Тутуш, брат Малик Шаха, стал властителем Сирийско-Палестинского государства от границ Египта до границ Антиохии, включая Иерусалим, Дамаск и Алеппо, и провозгласил себя султаном. Он поставил наместником Иерусалима своего военачальника Артука. После смерти Тутуша в 1095 г. его государство распалось, в Дамаске и Алеппо стали править его сыновья Дукак и Ридван, все более склонявшийся к шиизму, а в Палестине со столицей в Иерусалиме — сыновья Артука Сокман и Ильгази под верховной властью Дукака Дамасского.
В Анатолии между тем в 1092 г. возник могущественный султанат рум-сельджуков со столицей сначала в Иконии (Конья), а затем в Никее (Изник). Султан Кылыч Арслан (Сабля Льва), сын Сулеймана, отказался признать верховенство султана Больших сельджуков, и их отношения находились на грани войны. На северо-востоке Анатолии, в Месопотамии и Сирии, возник ряд мелких независимых турецких и арабских эмиратов и греко-армянских городов-владений.
Мусульмане в этническом отношении состояли из арабов, принявших мусульманство сирийцев, турок, туркмен, персов и курдов, пришедших из северо-восточного Ирана. Разнообразны были также мусульманские течения и секты: в Ираке, Иране и Месопотамии преимущественно жили сунниты, в Египте преимущественно — шииты (хотя большинство населения составляли христиане-копты), в Сирии и Палестине — те и другие, в горах Ливана — секта друзов. По пустыне бродили арабские племена язычников-бедуинов, склонявшихся к исламу. Ислам бедуины примут только в XVI в.