En los Acuerdos de Oslo, Israel y los palestinos acordaron construir aeropuertos en Cisjordania y la Franja de Gaza. Sin embargo, los acuerdos no contenían detalles específicos, como cuándo se construirían los aeropuertos ni qué tan grandes serían. Los palestinos comenzaron a trabajar en un gran aeropuerto en el sur de Gaza, que contrastaba con la expectativa de los israelíes de una pequeña instalación adecuada para vuelos locales.^[3]​

La construcción del aeropuerto comenzó el 20 de enero de 1996 cuando Yasser Arafat colocó la primera piedra. Tenía una pista de 3080 m de longitud y 60 m de ancho. Diseñado de acuerdo con los estándares de los aeropuertos internacionales de la OACI, podían recibir la mayoría de las aeronaves, incluido el 747. Japón, Egipto, Arabia Saudita, España, Alemania y Marruecos proveyeron dinero para la construcción del aeropuerto, que costó 86 millones de dólares y duró un año.^[4]​^[5]​ El aeropuerto fue inaugurado el 24 de noviembre de 1998 por el presidente Bill Clinton de los Estados Unidos y Yasser Arafat de la Autoridad Nacional Palestina.^[6]​^[7]​

Palestinian Airlines se trasladó a Gaza desde El Arish, Egipto, y operó el primer vuelo comercial a Ammán el 5 de diciembre.^[8]​ En ese momento, la apertura del aeropuerto fue descrita como una prueba del progreso hacia el Estado palestino y de la colaboración entre israelíes y palestinos.^[9]​^[10]​

El aeropuerto era operado por la Autoridad de Aviación Civil Palestina.^[11]​ Los pasajeros eran sometidos a controles de seguridad por soldados israelíes en el cruce de Rafah; luego, tomaban un autobús hasta la terminal para tomar su vuelo.^[12]​ En el año 2000, comenzaron las obras de otra terminal, denominada ala sur. Japón financió el proyecto. Israelíes y palestinos planearon gestionar conjuntamente la seguridad en la terminal para reducir la necesidad de viajeros de ir al cruce de Rafah.^[13]​

En 1999, el aeropuerto recibió 90.000 pasajeros y más de 100 toneladas de carga. En mayo de 2000, Palestinian Airlines conectaba Gaza con seis ciudades de la región, como Dubái y Lárnaca. Además, varias aerolíneas extranjeras, como Royal Air Maroc y Air Sinai, operaban en el aeropuerto.^[14]​

La Segunda Intifada estalló en septiembre de 2000, y el aeropuerto vio despegar su último vuelo en 2001.^[15]​ El aeropuerto civil fue destruido por las Fuerzas de Seguridad de Israel en 2001, durante la Intifada de Al-Aqsa. La estación de radar, la torre de control y la pista fueron destruidas.^[16]​ Por esto, el aeropuerto ya no está en funcionamiento. En marzo de 2002, la Organización de Aviación Civil Internacional reprendió a Israel por el ataque al aeropuerto.^[17]​ Ninguno de los países, han reclamado nunca a Israel una reparación, a pesar de que diferentes asociaciones hayan pedido una indemnización y reversión de lo dañado por Israel.^[18]​^[19]​

En pie solo quedaba la estructura del hall de llegadas, con sus arcos abiertos a los cuatro vientos en medio de un árido terreno.^[20]​

El pacto quedó en suspenso debido a los acontecimientos posteriores relacionados con Hamás. En 2006, la organización ganó las elecciones legislativas palestinas y secuestró a un soldado israelí.^[21]​  Este último incidente desencadenó un conflicto durante el cual Israel bombardeó el aeropuerto.^[15]​  Edificios como el ala sur, cuya construcción estaba a punto de terminarse, resultaron dañados. Las autoridades palestinas dejaron de proteger el aeropuerto.^[13]​ Hamás tomó el control de la Franja de Gaza al año siguiente, y los israelíes continuaron bombardeando el aeropuerto durante las guerras con el grupo.^[22]​

La gente robó equipos del lugar.^[22]​ También destruyeron la pista y la terminal para obtener escombros; el bloqueo israelí de Gaza había provocado una escasez de materiales de construcción.^[15]​

• Palestinian Airlines
• Aeropuerto Internacional de El Arish

•   Wikimedia Commons alberga una categoría multimedia sobre Aeropuerto Internacional Yasser Arafat.
• «Sitio web oficial» (enlace roto disponible en este archivo).