Зимой 1071 г. Роман подготовил мощную экспедицию против сельджукских гарнизонов в отобранных у Византии восточных пограничных крепостях, Хилат и Манзикерт. Прежде всего он надеялся на восстановление границы, а при удобном случае — и на разгром главных сил Алп Арслана в решающей битве. Когда в марте — апреле 1071 г. все приготовления были закончены, император предложил турецкому повелителю переговоры. Смысл византийских предложений сводился к возвращению султану города Иераполя, взятого ромеями в ходе кампании 1068 г. в обмен на снятие турками осады с Эдессы. Это позволило бы султану возобновить войну с Фатимидами, захватившими под шумок некоторые города в Сирии. Таким образом у Романа развязывались руки в наведении порядка в регионе и в отражении туркменских набегов. Первое посольство императора было подкреплено вторым, которое достигло Алеппо в мае. Послы настаивали на обмене городами, угрожая войной в случае отказа.
Роман уже оставил Константинополь и назначил сбор своих войск на конец февраля — начало марта. Ко времени прибытия второго посольства Арслан уже, должно быть, получил вести о походе византийской армии к границам Армении. Прервав переговоры с правителем Алеппо, он немедленно, лишь с собственным конвоем и маленькой свитой, отправился на восток, переправился через Евфрат, чтобы принять на себя командование войсками в Армении и Месопотамии и отразить нашествие ромеев.
Начало византийского похода сопровождалось некоторыми событиями, которые не предвещали экспедиции успеха. Во-первых, Роман оставил не у дел Никифора Вотаниата, способного полководца, которого он подозревал в нелояльности. Во-вторых, он взял с собой в поход Андроника Дуку, старшего сына Иоанна Дуки, одного из главных претендентов на престол, который уж точно был к нему нелоялен. В то же время Роман все дальше удалялся от собственных солдат и офицеров. Он не только отказался делить с ними тяготы похода, но и повелел на каждой стоянке разбивать для себя, своего конвоя и свиты отдельный лагерь, и даже завел специальный обоз, перегруженный сложными материалами и обстановкой для собственного шатра. На марше от реки Халис до Севастии императорская охрана из немецких наемников была несколько потрепана партизанскими атаками ограбленных ими жителей. Роман был вынужден призвать своих телохранителей к порядку, окружив их лагерь верными войсками. Затем последовало расформирование части, с распределением солдат в гарнизонную службу, подалее от театра военных действий. В то же время в Севастии император обрушил репрессии на местное армянское население, которое он обвинил в участии вместе с сельджуками в налетах на византийскую территорию в предыдущем году.
К концу июня имперская армия достигла Эрзерума (Теодозиополиса), где надлежало уточнить стратегический план кампании и выбрать направление главного удара. На военном совете мнения резко разделились. Некоторые командиры предлагали продолжать поход, перенеся военные действия вглубь неприятельской территории, и выйти в тыл главным силам султана, принудив его, таким образом, к решающей битве.
Сторонники наступления исходили из последних сообщений шпионов из ставки Арслана о том, что он в панике бежал из Алеппо, и предполагалось, что он должен будет сначала вернуться в Ирак, чтобы собрать там войска для сопротивления ромеям. Другие, включая Иосифа Тарханиота и Никифора Вриенния, настаивали, что надо ждать развития событий, укрепляя окрестные города и усилив их гарнизоны, а лежащая впереди местность должна быть полностью опустошена, чтобы лишить приблизившуюся турецкую армию всяких поставок. Этот план был отвергнут из опасения, что слишком долгое ожидание неприятеля приведет к истощению припасов собственно византийской армии, и был отдан приказ выступать.
Точно подсчитать численность императорской армии трудно. Ясно, что далеко не все войска Византии приняли участие в походе. Часть личных гвардейцев императора — варангов (варягов) — оставили в роскошном Константинопольском дворце; франкская тяжелая конница при своем командире Криспосе была оставлена в Абидосе; поскольку и норманны и венгры были постоянной угрозой спокойствию ромейского мира на Балканах, гарнизоны в этих областях не уменьшались. Возможно, что именно туда и отправился проштрафившийся немецкий контингент. Полевые армии в Сирии, в особенности те войска, которые находились под личным командованием военного правителя в Антиохии, оставались нетронутыми, и в свете последующих событий некоторые подкрепления в главную армию будут посланы именно оттуда.
Источники того времени свидетельствуют, что после сражения значительные силы еще оставались в составе гарнизонов по всей Анатолии.