Весной 960 года Никифор собрал свою армию в Фигелах к югу от Эфеса. Настрой был хорошим, поскольку солдаты любили своего командующего: считалось, что он заботится о людях. Во время военных кампаний Никифор разделял с ними все тяготы и невзгоды. Однажды, отдав приказ о строительстве укреплений на холме, он сам потащил первый тяжелый строительный блок вверх по склону и велел всем солдатам сделать то же самое. Неудивительно, что войска обожали его и прозвали «Белая смерть сарацин». Вряд ли Никифор был харизматичной личностью: низкорослый, сутулый, с густыми черными бровями и крючковатым носом. Один из его врагов отозвался о нем как о человеке, «с которым вы не захотели бы встретиться в темноте». Не была основана его популярность и на грубых шутках с солдатами. Наоборот, даже в обществе, где вера занимала важнейшее место в жизни каждого, Никифор выделялся своим благочестием. Он мог молиться всю ночь, стоя, и всегда спал на полу в ночь перед причастием. Призвание солдата доместик считал недостойным и страстно желал стать монахом. Больше того, он собирался принять постриг, как только кампания на Крите успешно завершится. В то время как шла подготовка к вторжению, Никифор совершил плавание через Эгейское море к полуострову Афон в Северной Греции, где испросил духовного совета у нелюдимого отшельника Афанасия.
Но, несмотря на весь свой религиозный пыл, Никифор Фока не пренебрегал воинским долгом. Он тщательно продумывал тактику и стратегию – даже написал книгу на эту тему. Все свои знания и опыт Никифор применил при подготовке к экспедиции на Крит. Когда все было готово, войско погрузилось на корабли. Такая большая флотилия не могла подойти к острову скрытно, и арабы ждали на берегу, готовясь напасть, когда захватчики окажутся в наиболее уязвимом положении – при высадке на берег. Никифор, однако, подготовился к этому. Он оснастил суда трапами, так что близко к берегу и пехота, и кавалерия смогли сойти с кораблей в полной боевой готовности. Арабы были столь поражены увиденным, что отошли, и наступление начали византийцы, заставив в конце концов арабов укрыться за стенами их столицы, города Хандак. За зиму 960–961 годов армия Никифора сумела занять большую часть острова и начала осаду Хандака.
Когда весть об этом достигла Большого дворца, реакция там была неоднозначной. Естественно, началось ликование, поскольку происходящее означало, что Крит, скорее всего, будет возвращен Византии, но в то же время поползли слухи, будто прославленный полководец намеревается воспользоваться своей победой, чтобы захватить престол. Главный министр императора, евнух Иосиф Вринга, который ведал всеми делами государства, особенно встревожился и стал убеждать Романа II отозвать своего опасного подданного. К счастью, Роман не внял совету Вринги, и в марте 961 года осаждающие войска ворвались в стены крепости. Крит был возвращен Византии.