 In 634 , Gaza was besieged by the Rashidun army under general ' Amr ibn al- ' As , with assistance from Khalid ibn al @-@ Walid , following the Battle of Ajnadayn between the Byzantine Empire and the Rashidun Caliphate in central Palestine . The Muslims ' victory at Ajnadayn gave them control over much of Palestine 's countryside , but not the major cities with garrisons such as Gaza . With Umar succeeding Abu Bakr as caliph ( head of the Caliphate ) , the Rashidun forces began to make stronger efforts at conquering Byzantine territory . During the three @-@ year siege of Gaza , the city 's Jewish community fought alongside the Byzantine garrison . In the summer of 637 , Amr 's forces broke the siege and captured Gaza , killing its Byzantine garrison , but not attacking its inhabitants . Amr 's victory is attributed to a combination of Arab strategy , Byzantine weakness , and the influence of Gaza ’ s Arab residents . Believed to be the site where Muhammad 's great grandfather Hashim ibn Abd Manaf — who also lived as a merchant in Gaza — was buried , the city was not destroyed by the victorious Arab army . 
