fell to the Muslim armies in late 637, and by then the Muslims occupied the whole of northern Syria, except for upper Mesopotamia, which they granted a one-year truce. At the expiration of this truce in 638–639, the Arabs overran Byzantine Mesopotamia and Byzantine Armenia, and terminated the conquest of Palestine by storming Caesarea Maritima and effecting their final capture of Ascalon. In December 639, the Muslims departed from Palestine to invade Egypt in early 640. Arab conquests of North Africa: 639–698 Conquest of Egypt and Cyrenaica By the time Heraclius died, much of Egypt had been lost, and by 637–638 the whole of Syria was in the hands of the armies of Islam. With 3,500–4,000 troops under his command, 'Amr ibn al-A'as first crossed into Egypt from Palestine at the end of 639 or the beginning of 640. He was progressively joined by further reinforcements, notably 12,000 soldiers by Zubayr ibn al-Awwam. 'Amr first besieged and conquered Babylon Fortress, and then attacked Alexandria. The Byzantines, divided and shocked by the sudden loss of so much territory, agreed to give up the city by September 642. The fall of Alexandria extinguished Byzantine rule in Egypt, and allowed the Muslims to continue their military expansion into North Africa; between 643 and 644 'Amr completed the conquest of Cyrenaica. Uthman succeeded Caliph Umar after his death. According to Arab historians, the local Christian Copts welcomed the Arabs just as the Monophysites did in Jerusalem. The loss of this lucrative province deprived the Byzantines of their valuable wheat supply, thereby causing food shortages throughout the Byzantine Empire and weakening its armies in the following decades. The Byzantine navy briefly won back Alexandria in 645, but lost it again in 646 shortly after the Battle of Nikiou. The Islamic forces raided Sicily in 652, while Cyprus and Crete were captured in 653. Conquest of the Exarchate of Africa In 647, a Rashidun-Arab army led by Abdallah ibn al-Sa’ad invaded the Byzantine Exarchate of Africa. Tripolitania was conquered, followed by Sufetula, south of Carthage, and the governor and self-proclaimed Emperor of Africa Gregory was killed. Abdallah's booty-laden force returned to Egypt in 648 after Gregory's successor, Gennadius, promised them an annual tribute of some 300,000 nomismata. Following a civil war in the Arab Empire the Umayyads came to power under Muawiyah I. Under the Umayyads the conquest of the remaining Byzantine and northern Berber territories