Алп-Арслан (его имя означает «Храбрый Лев») был племянником великого военного вождя сельджуков Тогрильбега. Он отличался большим знанием дела, хотя судьба не всегда была благосклонна к нему в войнах против Византии. Но он был тем полководцем, который умел извлекать уроки из поражений.
Близ города Себастия (современный Сивас в Турции) состоялась большая битва. Турки были разгромлены, хотя больших потерь не понесли. Их спасло то, что легкая восточная конница удачно выходила из-под обстрела византийских лучников и во многих случаях могла избежать продолжительных схваток с тяжелой панцирной кавалерией противника. Сельджукам пришлось отступить от Себастии.
Византийцы победили во многом благодаря своей организованности и дисциплинированности. Туркам пришлось через несколько дней уйти еще дальше от Себастии – в Армению и Месопотамию. Султан Алп-Арслан разумно избежал нового сражения с армией базилевса.
Тот, успешно отразив набеги сельджуков на Каппадокию, двинулся в поход на восток, вошел в земли Армении и осадил сильную крепость Ахлат на берегу озера Ван. Турецкий гарнизон сдаться отказался, надеясь на обещание султана в самом скором времени прийти на выручку.
Однако вскоре Романа IV постигла неудача: часть армии он отправил из осадного лагеря в Мидию, где Алп-Арслан разбил ее в сражении. Сельджуки удачно выбрали место для битвы на пустынной равнине среди таких же пустынных гор. Их конница продемонстрировала на поле битвы все искусство стремительного маневрирования, в нужный момент зайдя за фланги византийцев.
Базилевсу пришлось снять осаду с Ахлатской крепости и двинуться навстречу султанской армии. В то время войска Алп-Арслана вторглись в Анатолию, нанося удар в направлении города Икония (современный Конья). Сельджуки торопились захватить его до подхода византийцев.
Базилевс блестяще обыграл своего опытного соперника, совершив обходной маневр. Византийская армия, имевшая хороших проводников, неожиданно зашла в тыл неприятелю.
Близ современного турецкого города Эрегли, называвшегося тогда Гераклеей, произошло большое сражение. Византийцы одержали убедительную победу, но не воспользовались в полной мере ее результатом, позволив сельджукам отступить и не став их преследовать. Султанские войска отошли на север Сирии к городу Алеппо.