В то время как правители Византии были заняты противостоянием с Симеоном, царем Болгарии, в Малой Азии находились воители, которые пользовались возможностями, открывшимися на Востоке. Человеком, возглавившим контрнаступление, был Иоанн Куркуас, семья которого владела землями вокруг Докеи в феме Армениакон. В 919 году он помог Роману Лакапину захватить власть в Константинополе, и наградой ему стало назначение на относительно новый пост доместика восточных схол – главнокомандующего армии на восточной границе. Одновременно с этим постом появился и новый вид войск, более востребованный в изменившихся условиях. По мере того как Византия переходила на восточной границе от обороны к наступлению, прежние войска фем все больше морально устаревали. Они были созданы для того, чтобы отражать нападения арабов на земли Малой Азии, не перенося боевые действия на территорию противника за Таврские горы. Их солдаты были одновременно земледельцами, что обеспечивало им пропитание. Вместо этих войск стала расширяться регулярная армия, тагмата, основанная Константином V. Этим солдатам платили жалованье из имперской казны, а не наделяли земельными участками, и улучшение их экономического положения вызвало приток желающих записаться в войско. Среди вербовавшихся в этот элитный полк оказывалось все больше чужеземцев, рожденных за пределами Византийской империи. Особенно много было русов, но встречались даже и арабы. Анема, сын эмира Крита, входил в число императорских стражников и погиб, сражаясь за императора в Болгарии в 971 году. Появление на службе наемников не было признаком слабости или упадка, но следствием экономического возрождения, позволившего византийцам покупать лучших солдат, а также их исключительной способности интегрировать чужаков и обращать их воинственность себе на пользу. Роль тагматы также менялась. Раньше ее полки – тагмы – базировались вокруг Константинополя, во многом на тот случай, если взбунтуются стратиги фем, но теперь они переместились на восточные окраины, где от них было больше пользы. Командовал ими доместик схол, так что Куркуас полностью контролировал императорскую армию на востоке и потому был влиятельнее, чем стратиги фем.
В течение 920-х годов Куркуас регулярно совершал набеги на приграничные арабские города, но его главной целью была Мелитена, которая много лет служила арабам надежным убежищем на западе Таврских гор во время их рейдов в Малую Азию. В мае 934 года Куркуас вторгся на земли Мелитены, захватил их и осадил город, и в конце концов губернатор сдался и открыл ворота. Куркуас вручил город и его окрестности императору Роману, который принял их как владение империи, а не разделил земли между воинами, как делалось в прошлом. Так было выгоднее для сбора налогов, позволявших платить элитным войскам. Сделав Мелитену неопасной, Куркуас смог повести свои войска за пределы Византии в Сирию. В 943 году он окружил город Эдесса, находившийся далеко на арабской территории. Понимая, что помощи в ближайшем будущем ждать неоткуда, жители были готовы к переговорам. В обмен на свою безопасность они предложили отдать драгоценный Мандилион, древний плат, на котором сохранился отпечаток лица Христа. Куркуас был рад согласиться и, сняв осаду, ушел в Таврские горы. Реликвию торжественно привезли в Константинополь в августе 944 года и поместили в храме Богородицы Фарской. Для византийцев обладание Мандилионом оказалось значимее, чем взятие Мелитены. Куркуас стал героем, и о нем и его победах даже был написан труд в восьми томах. Но нашлись и те, кто взирал на успехи Куркуаса с тревогой. Пока на востоке империи добывались победы, в Большом Константинопольском дворце события развивались своим чередом.