Arap devletleri, 1964 yılında bir araya gelerek Filistin Kurtuluş Örgütü'nü kurdular. Amaçları, giderek radikalleşen ve kendileriyle birlikte tüm Arap halklarını da radikalleştiren Filistinlileri kontrol etmekti. Ne var ki, Filistin kurtuluş hareketi, kısa zamanda tam anlamı ile denetlenebilir bir örgüt olmaktan çıktı. Başında Arafat'ın bulunduğu El Fetih, FKÖ'nün temel örgütü hâline geldi.
FKÖ'nün temelleri Ocak 1964'te Kahire'de toplanan Arap Zirvesi ile atıldı. FKÖ'nün kurulmasına Filistinli mücadeleci örgütler değil, Arap hükümetleri öncülük etti. Burada amaç, giderek radikalleşen Filistinlileri kontrol altına almaktı. Çünkü Filistinliler, kendileriyle birlikte bütün Arap halklarını da radikalleştirmeye başlamışlardı. Bu da Arap egemenleri için tehlike çanlarının çalması anlamına geliyordu.
FKÖ'nün kurumsallaşması aşamasında, Arap devletleri Filistinlileri mücadele yönünde yetiştirmek amacıyla askeri okullarına alma talebinde bulundular, ayrıca teşkilatın finansmanı için bir Filistin Milli Fonu oluşturuldu. Arap devletlerinde FKÖ'nün ofisleri açıldı ve o sıralarda Gazze ve Sina'da üslenecek bir Filistin Kurtuluş Ordusu kuruldu.
Bir anlamda Filistin davasının siyasal temsilcisi olan ve çok sayıda Filistinli örgütü bir çatı altında toplayan FKÖ, 1967 Arap-İsrail Savaşı'nda etkinliğini artırdı. 1968 yılında yapılan Filistin Ulusal Konseyi'nin dördüncü toplantısında FKÖ yeniden örgütlendi. Komando grupları üye yapılırken, sözleşme yeniden gözden geçirildi ve Filistin Kurtuluş Ordusu'nun komando kanadı kuruldu.
Mart 1968'de 200 FKÖ fedaisi, ağır silahlara ve tanklara sahip İsrail birliklerine karşı Ürdün-İsrail sınırındaki Karameh kasabasında 12 saat boyunca direndi ve İsrail birliklerini geri püskürttü. Bu zafer sonrasında Filistinliler, Ürdün'de en ciddi güç hâline geldiler. Tahtının sallandığını düşünen Ürdün kralı Hüseyin, ABD'den aldığı silahlarla Filistinlilere saldırdı. "Kara Eylül" olarak bilinen bu olayda üç bin kadar Filistinli öldü, on binlercesi Lübnan'a kaçmak zorunda kaldı.
FKÖ şemsiyesi altında bulunan gruplar içindeki en büyük örgüt olan El-Fetih'in lideri Arafat, "Kara Eylül" sonucunda sağa kaydı ve Arap rejimleriyle daha yakın ilişkiler kurdu. Çeşitli Arap ülkeleri, çeşitli Filistinli örgütlerin finansörü haline geldi. FKÖ'ye en büyük yardım Suudi Arabistan, Kuveyt ve Arap şeyhliklerinden geliyordu, çünkü bu ülkelerde yaşayan Filistinli göçmenler, petrol sanayinin ucuz işgücünü oluşturuyordu.
1974 yılında örgüt, Arap Birliği, İslam Konferansı Örgütü (İKÖ) ve BM tarafından Filistinlilerin tek meşru temsilcisi olarak tanındı. 1980'li yılların başlarına kadar FKÖ pek çok değişik grubu bünyesinde taşıyor olmasına rağmen Filistinlilerin önde gelen örgütü olma özelliğini korudu. Örgütün merkezi 1967 savaşından sonra Ürdün'e, 1970'te Lübnan'a ve 1982 yılında İsrail'in Lübnan'ı işgaliyle Tunus'a taşındı.
1987 yılında işgal atındaki topraklarda başlayan intifada esnasında FKÖ yönlendirici bir rol oynamadı. Örgüt giderek taleplerinin sınırlarını geri çekmeye başladı. 1993 yılında yapılan bir dizi görüşme sonrasında geniş kapsamlı bir barış anlaşmasının zemini hazırlandı. 1994 yılında yapılan Gazze-Eriha Anlaşması ve Eylül 1995'te yapılan II. Oslo Anlaşması'yla İsrail Gazze Şeridi'nin tamamına yakınının, Batı Şeria'nın ise bazı bölgelerinin yönetimini Filistin Otoritesi'ne bıraktı. 1996 yılının Ocak ayında yapılan seçimlerin sonucunda 88 üyeli Filistin Otoritesi Konseyi oluşturuldu. Ayrıca seçimlerin sonunda Arafat Filistin Otoritesi'nin başkanı olarak göreve başladı. Filistin Otoritesi kabinesi 23 bakanlıktan oluşuyordu fakat önemli kararları alma yetkisi Arafat'a aitti. Ayrıca hükümette önemli pozisyonlar El-Fetih üyelerine verildi.
1998'de İsrail'in varlığını tanımayı reddeden maddeler FKÖ programından çıkartıldı. 2004 yılında Arafat'ın ölümüyle, Mahmud Abbas, FKÖ'nün yeni başkanı oldu. 2006'da yapılan seçimlerde FKÖ'nün içinde bulunan El-Fetih bozguna uğradı ve parlamentodaki çoğunluğunu yitirdi. Seçimlerin galibi Hamas oldu.
Filistinliler hâlâ büyük acılar çekiyorlar. Yolları, gıdaları, okulları, evleri, kısacası hiçbir şeyleri yok. Yine de geleceğe umutla bakıyorlar, günün birinde acılarının son bulacağına inanıyorlar. Bugün insan olmak, Filistin'e özgürlük istemek, Filistinlilerin yanında olmaktır.