From the ascension of Emperor Romanos II in 959, Nikephoros and his younger brother Leo Phokas were placed in charge of the eastern and western field armies respectively. In 960, 27,000 oarsmen and marines were assembled to man a fleet of 308 ships carrying 50,000 troops. At the recommendation of the influential minister Joseph Bringas, Nikephoros was entrusted to lead this expedition against the Muslim Emirate of Crete. Nikephoros successfully led his fleet to the island and defeated a minor Arab force upon disembarking near Almyros. He soon began a nine-month siege of the fortress town of Chandax, where his forces suffered through the winter due to supply issues. Following a failed assault and many raids into the countryside, Nikephoros entered Chandax on 6 March 961 and soon wrested control of the entire island from the Muslims. Upon returning to Constantinople, he was denied the usual honor of a triumph, being permitted a mere ovation in the Hippodrome.

The reconquest of Crete was a major achievement for the Byzantines, as it restored Byzantine control over the Aegean littoral and diminished the threat of Saracen pirates, for which Crete had provided a base of operations.