Согласно договору, заключённому в 1022 г. между византийским императором Василием II Болгаробойцем и царём Ованнесом Смбатом III, после смерти последнего царство должно было перейти под управление империи. Воспользовавшись выгодными условиями договора, византийцы присоединили Ани, лишив трона царя Гагика II и предложив ему взамен владения в Каппадокии. Они начали также притеснения Армянской Апостольской церкви, добиваясь признания византийского халкидонского православия и заключения унии. Однако, продвинувшись таким образом на восток, они вскоре столкнулись с новой угрозой. При Константине IX Мономахе на восточной границе впервые появились тюрки-сельджуки, которые в это время были объединены под властью султана Тогрул-бека, захватили значительную часть Центральной Азии и продолжали продвижение на Запад, угрожая всем государствам Ближнего Востока. Опасность их набегов для Византии при Константине IX Мономахе ещё не была оценена в полной мере. В 1048 г. произошло первое нападение тюрков-сельджуков, которое возглавили ближайшие родственники Тогрул-бека, его брат Ибрагим и племянник Кутулмыш. Военная кампания против них была неудачной; тюрки разбили катепана фемы Васпуракан Стефана Лихуда и захватили его в плен. В 1049 г. в плен к ним попал наместник Абасгии Липарит. В обмен на его освобождение Константин IX Мономах обещал Тогрул-беку построить (или восстановить) мечеть в Константинополе. Условия этого соглашения были исполнены, но мирный договор не был заключён. Набеги отдельных тюркских племён, неподконтрольных Тогрул-беку, а также большие походы Ибрагима и Кутулмыша продолжались регулярно. В 1050 г. катепан Ани Катакалон Кекавмен отбил нападение сельджуков, нанеся им поражение в битве. Но в 1052 г. Ибрагим захватил Феодосиополь (Эрзурум) и увёл в плен много жителей; в 1054 г. султан Тогрул-бек во главе войска осаждал Манцикерт, но был вынужден отступить под давлением превосходящих византийских сил. Таким образом, война шла с переменным успехом, но к середине 1050 гг. значительная часть приграничных земель Византии уже была опустошена сельджуками. В марте 1055 (или 1056) г., вскоре после смерти Константина IX Мономаха, был заключён договор, по которому Тогрул-бека начали поминать на пятничных молитвах в мечети в Константинополе наравне с багдадским халифом; также Византия объявила об отказе от союза с фатимидским Египтом, что было выгодно для сельджуков. В начале 1040 гг. византийцы успешно отстаивали свои владения в Южной Италии от натиска норманнов. В 1040–1043 гг. предприняли большую экспедицию на Сицилию, попытавшись отвоевать остров у арабов, но их наступление из-за действий командующего Георгия Маниака, который к началу правления Константина IX Мономаха уже потерял доверие константинопольского правительства и вскоре был смещён с поста, завершилось неудачно. В 1042 г. Аргир из Бари попытался поднять восстание против византийцев и заключить союз с норманнами, но вскоре был перекуплен Константинополем и окончательно перешёл на сторону империи. Норманны были изгнаны из Бари и нескольких других городов. Аргир, ставший наиболее влиятельным лицом в византийской Италии, заслужил полное доверие Константина IX Мономаха.