И все же, несмотря на меры, предпринятые на юго-восточной границе, проживавшие на территории Византийской империи сторонники ислама продолжали получать подкрепление от постоянно проникавших в укрепленную буферную зону воинственных мусульман и занимавшихся грабежами тюрок. Их действия осложняли жизнь греков, которым стало трудно поддерживать сообщение между населенными пунктами, а также обеспечивать безопасность городского и сельского населения этого региона. В нескольких районах мусульмане даже стали почти независимыми от центральной власти князьками, и это в совокупности со всем остальным заставило императора предпринять попытку (что имело место около 1000 года нашей эры) убедить грузинского и армянского правителей передать часть своих территорий ему. Царь Грузии Давид Курополат согласился отдать ему Иверию, и в 1020 году император рискнул обратиться с таким же предложением к правителю Армении. Переговоры с ним тянулись два года, но в итоге византийцу удалось убедить его в том, что сельджуки представляют собой серьезную опасность, и тот согласился уступить территорию своего царства в обмен на новое владение, расположенное в Тавре, со столицей в Севастии (Сивасе).
Возможно, император поступил бы мудрее, если бы позволил Армении и в дальнейшем самой заботиться о собственной безопасности. Дело в том, что в результате предпринятых его предшественником мер жесткой экономии военная машина Греции находилась в таком состоянии, что император просто не мог обеспечить защиту уже существовавших границ Византийской империи, уж не говоря о безопасности каких-то новых территорий. Тогрул обнаружил уязвимое место Византии в 1045 году, когда во время одного из походов сельджукам удалось дойти до берегов озера Ван и до Карса. В 1047 году византийцы с трудом отбили второе нападение Сельджукидов, целью которых на этот раз был Эрзурум. На следующий год сельджуки возобновили наступление, прорвали оборону города и перебили жителей. В 1049 году они разграбили Ани, в 1053-м вновь атаковали Каре, в 1056-м взяли Мелитену (Малатью), а в 1059-м даже совершили набег на Севастию.
Хотя все эти походы скорее следует считать рейдами, а не спланированными военными кампаниями, тем не менее они были очень хорошо организованы и в них принимали участие регулярные войска. Участники рейда собирались на заранее условленном месте, где их делили на четыре равные по силе группы. Затем группы выстраивали по сторонам квадрата, соответствующим сторонам света. После этого каждая группа выдвигалась в заранее обусловленную точку, где группу вновь делили, на этот раз уже на три равные по численности подгруппы. Со своих позиций все войско выступало одновременно, направление его движения было подобно направлению лучей раскрытого веера. Продвигаясь вперед, разбившееся на группы войско грабило и уничтожало все попадавшиеся на его пути селения до тех пор, пока намеченная цель не была достигнута. Затем сельджуки быстро отступали с награбленным, вновь собираясь в единое войско в полном соответствии с тем же принципом, согласно которому они выстраивались перед рейдом.
Хотя основной целью Алп Арслана было покорение Герата, он, в свою очередь, в 1064 году перешел реку Араке с тем, чтобы атаковать Ани – столицу последнего независимого эмира Карса. Он надеялся, что таким образом ему удастся помешать византийцам упрочить союз с его заклятыми врагами Фатимидами. Разрушив город, сельджуки повернули на юг, где разграбили Антиохию и Эдессу (Урфу), но на следующий год Алп Арслан возобновил набеги на Малую Азию. В 1067 году, одержав победу над армией византийцев у Левитане и Севастии, он штурмовал Кесарию (Кайсери). Вдохновленный успехом, в 1068 году он решил начать вторжение непосредственно на территорию Византийской империи. Поэтому на следующий год он напал на Иконий (Конью) и взял его, а через год атаковал Хонас на Эгейском море.
В это время в Византии правил император Константин Дука (1059–1067). Интеллектуальные пристрастия и демократические взгляды этого правителя-либерала разделял и во многом определял его бывший наставник Михаил Пселл, который в то время уже занимал пост первого министра. Вместе они совершили немало ошибок, и самой большой из них было значительное сокращение финансирования вооруженных сил. Результатом этого стало уменьшение офицерского жалованья и сокращение числа стоявших на довольствии резервистов, что в итоге привело к потере армией боеспособности. Сокращение финансирования негативно сказалось не только на воинстве, но и на тех, кто работал в его вспомогательных службах: в арсеналах и складах. Даже численность воинов пограничных гарнизонов сократилась до опасных пределов. Вскоре многие районы восточных провинций империи обезлюдели, и оказалось, что численность кочевников-туркмен и вождей небольших тюркских племен там превысила численность греческого населения.