Filistin Kurtuluş Örgütü, bağımsız bir Filistin Devleti kurmak amacıyla 1964'te oluşturuldu FKÖ'nün kuruluşu Arap Birliği'nin Kahire'deki bir toplantısında ilan edildi. Örgütün amacı silahlı mücadele yoluyla Filistin'in kurtuluşu olarak açıklandı.
FKÖ'nün ilk toplantısı 28 Mayıs 1964'te Kudüs'te yapıldı. Toplantıya katılan 422 Filistinli, Ahmet Şukayri'yi lider olarak seçti. Konferansta Filistin Ulusal Komitesi adıyla bir yasama organı, FKÖ İcra Komitesi, ulusal bir fon ve Filistin Kurtuluş Ordusu da kuruldu. Ayrıca Filistin'i özgürleştirmeyi amaçlayan ulusal bir sözleşme ile eve dönüş ve kendi kaderini tayin haklarının yer aldığı bir anayasa taslağı hazırlandı.
Aralık 1967'de Şukayri'nin istifasının ardından FKÖ liderliğine Yahya Hamudeh getirildi. Hamudeh'in halefi Yaser Arafat ise 1969'da örgütün başına geçti.
FKÖ, çeşitli Filistinli grupları birleştiren şemsiye bir teşkilata dönüşerek, dünya çapında Filistinlileri harekete geçirip, davaya uluslararası destek bulmaya odaklandı.
Eğitim, sağlık ve yardım kuruluşları kuran FKÖ, kendi güvenlik, istihbarat ve dış politika birimlerini kurarak devlet gibi örgütlendi.
Birleşmiş Milletler Genel Kurulu 14 Ekim 1974'te FKÖ'yü Filistin halkının tek meşru temsilcisi olarak tanıdı. Örgüt, 28 Ekim 1974'te Arap Birliği Rabat Zirvesi'nde de aynı sıfatla tanındı. FKÖ, 15 Kasım 1988'te Cezayir'den Filistin'in bağımsızlığını ilan etti.
Aralık 1988'te FKÖ, İsrail'i tanıyarak teröre son verdi. Bunun karşılığında İsrail, 1993'te FKÖ'yü Filistin halkının meşru temsilcisi olarak tanıdı.
FKÖ lideri Arafat, 11 Kasım 2004'te öldü. Örgüt, Arafat'ın ölümünden beri Mahmut Abbas tarafından yönetiliyor.