В конце июня 960 года огромный флот поднял паруса, и Никифор направился прямиком в крупнейший на Крите город Кандия, после взятия которого можно было не ожидать серьезного сопротивления. Через пару дней началась осада, продолжавшаяся восемь месяцев. С наступлением зимы, самой долгой и суровой за много лет, дух осажденных начал слабеть. Единственным утешением для них был вид полузамерзших врагов, теснящихся вокруг костров: они знали, что зимы часто причиняют гораздо больше неудобств осаждающим, а не осажденным. Однако Никифору во время ежедневных обходов каким-то образом удавалось придать своим людям сил и вселить в них надежду и мужество. Его самого вдохновлял его друг Афанасий, которого он спешно призвал к себе с Афона. Никифор был убежден, что именно благодаря заступничеству Афанасия в середине февраля из Константинополя прибыл долгожданный флот с припасами; боевой дух византийцев был возрожден, город пал, и 7 марта 961 года знамя империи вновь развевалось над Критом – впервые за 136 лет. Последовала традиционная массовая резня, и флот с победой отправился обратно на Босфор, доверху нагруженный плодами грабежей, которые больше века совершал один из богатейших городов Восточного Средиземноморья.
Падение Кандии и последующий крах сарацинской власти на Крите стали для византийцев беспрецедентной победой со времен Ираклия. Когда весть о ней достигла Константинополя, в храме Святой Софии устроили всенощную благодарственную службу, на которой присутствовали император и императрица. Среди многочисленных собравшихся в храме был один человек, испытывавший не ликование, а тревогу. Евнух Иосиф Вринга всегда ненавидел дом Фока, а Никифор Фока внезапно стал для императора героем. Одержавшие победу военачальники были в лучшем случае опасны; чтобы сдерживать его честолюбие, за ним придется пристально следить, так что евнуха ждали несколько трудных недель. Вот так и вышло, что, когда Никифор Фока гордо проплыл через Золотой Рог, его приветствовали Роман и Феофано, публично поздравившие его с этим историческим достижением, однако в его честь не устроили полномасштабного праздника, которого он ожидал и заслуживал. Вместо этого ему дали понять, что ему не следует оставаться в столице дольше, чем это необходимо: империя должна как можно скорее продолжить наступление, и Никифор нужен на востоке.
Когда Никифор покинул свой пост на востоке, чтобы подготовиться к Критской экспедиции, командование взял на себя его младший брат Лев, который почти сразу столкнулся с серьезным вызовом со стороны давнего врага империи, эмира Мосула Сайф ад-Даулы. В 944 году Сайф захватил Алеппо, сделав его своей ставкой, и оттуда быстро расширил свои владения, в которые вошли большая часть Сирии и Северной Месопотамии, включая Дамаск, Эмесу и Антиохию. Еще не достигнув тридцатипятилетия, он уже стал образцом арабского эмира эпохи раннего Средневековья: жестокий и беспощадный в войне, рыцарственный и милосердный в мирное время, поэт и ученый, покровитель литературы и искусств, владелец самой большой конюшни, самой дорогой библиотеки и самого пышного гарема в мусульманском мире. Каждый год он непременно устраивал хотя бы один крупный набег на территорию империи; однако ни один из этих набегов не был столь амбициозным, как в 960 году. Время было выбрано идеально: восточная армия Византии серьезно поредела из-за Критской экспедиции, Лев Фока находился на расстоянии нескольких дневных переходов. Почти в то же самое время, когда Никифор отплыл на Крит, Сайф перешел границу во главе войска численностью около 50 000 человек. Лев последовал за ним, но его люди был измотаны после тяжелой кампании. Он продвинулся лишь до гор, где тщательным образом расположил своих людей на всех главных проходах и приготовился ждать.
Сайф со своей армией вернулся в начале ноября. Его поход оказался триумфальным: позади войска тащились длинные вереницы пленников и нагруженные добычей повозки; сам он гордо ехал во главе войска на великолепной арабской кобыле. Когда он въехал в ущелье, зазвучала невидимая труба, и через несколько секунд по склонам ущелья на беззащитную колонну полетели огромные валуны. Поначалу Сайф упорно продвигался вперед, но когда увидел, что терпит поражение, развернулся и ускакал, за ним последовали около трехсот его всадников. Почти половина из оставшихся были мертвы; выживших связали теми же веревками и кандалами, которые были на христианских пленниках.