В 637 г. Газа была взята арабским полководцем Амром ибн аль-Асом. Захваченные в плен солдаты гарнизона отказались перейти в ислам и были перебиты. В эпоху халифата Газа входила в состав Палестинского округа. Она редко упоминается в источниках, но очевидно, что город потерял роль центра виноторговли, и его экономические связи были переориентированы от Средиземноморья на внутреннюю Сирию и Египет. Среди мусульман город почитался как место смерти и погребения прадеда пророка Мухаммада Хашима, часто приходившего в Газу с мекканскими караванами. В 767 г. в Газе родился Мухаммад Идрис аш-Шафии, крупнейший юрист, один из создателей мусульманского права. Разрозненные свидетельства указывают на сохранявшееся христианское присутствие в Газе и Маюме. Во второй трети VIII в. известен поэт-гимнограф епископ Косма Маюмский, сводный брат Иоанна Дамаскина. Из Маюмы происходил мученик конца VIII в. Вакх Новы, выходцы из Газы упоминаются в Житиях палестинских монахов эпохи халифата. В конце VIII в. Газа с округой были опустошены в ходе междоусобной войны арабских племён Палестины. Однако Газа снова возродилась; путешественники X в. описывают её как большой и богатый город с прекрасной соборной мечетью. Газа в VII–X вв. занимала территорию в 90 га и насчитывала предположительно 25–30 тыс. жителей. В эпоху Крестовых походов борьба за район Газы началась сразу же после захвата Иерусалима крестоносцами в 1099 г. Под Газой и Рамлой неоднократно происходили сражения христианских и мусульманских армий. Крестоносцы овладели руинами Газы лишь в 1152 г. Они отстроили цитадель, разместили в ней гарнизон тамплиеров. Неукреплённая часть города была разорена в 1170 г. Салах ад-Дином, цитадель сдалась ему в 1187 г., после падения Иерусалима. Отбитая английским королём Ричардом I, она снова отошла мусульманам по договору 1229 г. В 1239 и 1244 гг. неподалёку от Газы крестоносцы потерпели поражения от мусульман. Во время вторжения в Палестину монголов (1260 г.) Газа стала крайней точкой их продвижения. В том же году монголы были выбиты из города египетскими мамлюками. В египетском султанате Газа – административный центр одной из провинций; иногда входила в провинцию Дамаск. Путешественники XIV–XV вв. пишут о её процветании, об окрестных садах и о виноградниках, торговле, мечетях, больницах и караван-сараях. В начале XIV в. на фундаменте церкви св. Иоанна, оставшейся со времён крестоносцев, была возведена новая соборная мечеть, простоявшая до Первой мировой войны. В мамлюкскую эпоху в Газе сохранялась православная община, возглавлявшаяся митрополитом. Русский паломник купец Василий в 1465 г. отмечал многочисленность местных христиан и упоминал городскую церковь Пречистой Богородицы.