In the years after the initial landing, the Byzantine Empire launched repeated expeditions to drive them back and recover the island, but these were defeated.

It made some headway, and apparently allowed for the re-establishment of the recovered parts of the island as a theme, as evidenced by the presence of a strategos of Crete in the contemporary Taktikon Uspensky.

[11][12] According to Christos Makrypoulias, despite their often meticulous preparation, the Byzantine expeditions against Crete failed due to supply constraints and the strategy of attrition followed by the Cretan Saracens.

[13] Determined to avenge the disaster of 949, towards the end of his reign Emperor Constantine VII Porphyrogennetos (r. 913–919, 945–959) renewed preparations for capturing the island.

With the support and urging of his chief minister, Joseph Bringas, Romanos pushed on and appointed the Domestic of the Schools of the East, Nikephoros Phokas, a capable soldier and a distinguished veteran of the wars against the Muslims in eastern Asia Minor, as the commander-in-chief of the expedition.

[16] This expedition was far larger than previous ones, chiefly due to the relative internal stability brought on by recent victories on the eastern frontiers and a longstanding peace with the Bulgarians.

[18] The otherwise unknown Theodosios the Deacon wrote his poem in 961/962, as a panegyric to the recapture of the island, and presented it to Nikephoros Phokas shortly before his ascent to the imperial throne in 963.

[18][19] Leo the Deacon, who was born c. 950, completed his history after 992, and is a major Byzantine source on the period 959–975, including many anecdotes and eyewitness accounts.

It does not survive in its original form, but in two variants: one as the sixth and last book of the Theophanes Continuatus, that deals with the reign of Constantine VII and Romanos II up to the spring of 961, and a summarized version up to 962 as part of the chronicle of Pseudo-Symeon.

Nikephoros quickly mustered his troops in the typical Byzantine battle formation in three sections, and charged the Saracen army.

For it was built of earth, and goat and pig hair, mixed together and compressed thoroughly; and it was wide enough so that two wagons could easily make a circuit on top of the ramparts and pass each other, and it was quite high, and in addition two extremely wide and deep moats were dug around it.From Leo and Theodosios' account it appears that Nikephoros initially hoped to capture Chandax by storm, but when this failed, he settled for a long-term siege,[28] constructing a fortified encampment in front of Chandax, and placing his fleet in a secure anchorage nearby with orders to blockade the city and destroy any ships that might try to leave it.

[29] According to Leo, Phokas then instructed Nikephoros Pastilas, the strategos of the Thracesian Theme and a distinguished veteran of the wars against the Arabs in the east, to take a "cohort of picked men" and undertake a raid into the Cretan countryside to scout out the situation and gather supplies.

[34] The Arab relief army was annihilated, and Phokas instructed his men to cut off the heads of the fallen and take them with them as they returned to their base, again moving only during the night.

The sight caused great consternation and lamentation among the inhabitants, who saw their kin and friends dead; but they remained determined to resist, and threw back an attack led by Phokas soon after.

He wrote letters to Romanos demanding that his forces leave Crete, otherwise the truce signed between them in 958 would be ended; and to Unujur suggesting a common effort against the Byzantines by uniting their fleets on 20 May 961 at Tolmeita in the Cyrenaica.

[3][41] Lying on the southern entry of the Aegean Sea, the conquest of Crete was especially beneficial to the Byzantines due to its strategic position for the purpose of launching raids onto the coast of North Africa.