Organizatë kombëtare palestineze e themeluar më 1964, pas një propozimi të presidentit egjiptian Gamal Abdel Nasser në një takim të nivelit të lartë arab. Qëllimi fillestar ishte çlirimi i Palestinës, krijimi i një shteti për arabët palestinezë dhe zëvendësimi i shtetit të Izraelit. Mbreti Hussein i Jordanisë druhej se krijimi i një «entiteti palestinez» do të vinte në pikëpyetje sundimin jordanez mbi Bregun Perëndimor. Këtë territor Jordania e kishte marrë nën kontroll gjatë luftës arabo-izraelite të vitit 1948 dhe e kishte aneksuar më 1950, gjatë mbretërimit të gjyshit të tij, Abdullahut. Në dokumentet themeluese të OÇP-së u shmang formulimi «entitet palestinez» dhe u përdor shprehja «çlirimi i Palestinës».

OÇP-ja duhej të luante një rol të efektshëm në çlirimin e Palestinës, por qeveritë arabe, veçanërisht Nasser-i, synonin gjithashtu t'i kanalizonin energjitë dhe shpresat e palestinezëve brenda një organizate që mund ta ndikonin. Ato donin të kufizonin përdorimin e pavarur të dhunës nga grupet palestineze. Veprimtaria guerile kundër Izraelit, që kishte filluar të merrte formë në fund të viteve 1950 dhe po bëhej faktor i politikës rajonale në vitet 1960, mund të sillte kundërgoditje izraelite ndaj vendeve arabe. Frika ishte se këto goditje do t'i përfshinin qeveritë arabe në një luftë për të cilën nuk ishin të përgatitura.

Karta Kombëtare Palestineze e vitit 1964 i përkufizonte arabët palestinezë si pjesë të kombit arab me të drejtë mbi atdheun e tyre. Ajo quante palestinezë qytetarët arabë që kishin banuar përherë në Palestinë deri më 1947 dhe pasardhësit e tyre në vijën atërore, kudo që të lindnin. Në këtë version të kartës përfshiheshin edhe hebrenjtë me prejardhje palestineze që pranonin të jetonin paqësisht dhe besnikërisht në Palestinë. Karta e shpallte të pavlefshëm ndarjen e Palestinës dhe krijimin e shtetit të Izraelit dhe kërkonte që palestinezët të formonin një front të bashkuar për çlirimin e vendit. Këto ishin qëndrimet programore të organizatës në atë periudhë; ato duhen dalluar nga njohja e mëvonshme e Izraelit prej OÇP-së.

Në vitet e para, organizata ndërtoi një kuadër institucional për veprimtaritë shoqërore, ekonomike, politike, kulturore, arsimore dhe ushtarake të palestinezëve. Krijoi edhe një ushtri, pjesë të së cilës iu bashkëngjitën ushtrive të shteteve të ndryshme arabe. Megjithëse nuk zotëronte territor sovran, OÇP-ja mori përsipër gradualisht plotësimin e shumë nevojave të një popullsie të shpërndarë. Ndërtimi i këtyre strukturave synonte si përgatitjen për shtetësi, ashtu edhe arritjen e saj në Palestinë.

Besimi se qeveritë arabe do t'ua rikthenin palestinezëve tokat e humbura kishte filluar të dobësohej në vitet 1950. Humbja ushtarake arabe në Luftën Gjashtëditore të qershorit 1967 e thelloi këtë mosbesim. Grupet guerile palestineze, të njohura si fedainë, fituan rëndësi më të madhe. Ndër organizatat kryesore ishin Fatah-u, Lëvizja Kombëtare për Çlirimin e Palestinës, e krijuar në vitet 1957–1958 dhe e drejtuar nga Yasser Arafat; Fronti Popullor për Çlirimin e Palestinës, i udhëhequr nga George Habash; dhe Fronti Demokratik për Çlirimin e Palestinës, i udhëhequr nga Nayef Hawatmeh. Në kuadrin e mëvonshëm politik palestinez përfshihej edhe Partia e Popullit Palestinez, e cila e mori këtë emër më 1991 nga Partia Komuniste Palestineze e themeluar më 1982; ajo nuk ishte një organizatë fedainësh e krijuar menjëherë pas luftës së vitit 1967.

Qysh në periudhën e themelimit të OÇP-së më 1964, Fatah-u mbronte domosdoshmërinë e luftës së armatosur për rikthimin e Palestinës, duke kundërshtuar varësinë nga qeveritë arabe. Organizata e bojkotoi zyrtarisht kongresin themelues të majit 1964. Me rritjen e numrit të përkrahësve të fedainëve, grupet e armatosura arritën të mbizotëronin në OÇP më 1968. Në sesionin e Këshillit Kombëtar Palestinez të vitit 1969, Arafati u zgjodh kryetar i Komitetit Ekzekutiv. OÇP-ja u bë kështu një organizatë ombrellë për shumë grupe fedainësh, drejtuesit e të cilave hynë në Komitetin Ekzekutiv, ndërsa lufta e armatosur u bë strategjia e saj mbizotëruese.

Ky ndryshim ndodhi në kushtet e krijuara nga lufta e vitit 1967. Izraeli kishte marrë nën kontroll Lartësitë e Golanit, Bregun Perëndimor dhe Jerusalemin Lindor, duke kontrolluar kështu të gjithë Jerusalemin, si edhe Gazën dhe Gadishullin e Sinait. Përballja me Egjiptin vazhdonte nëpërmjet një armëpushimi të pasigurt përgjatë Kanalit të Suezit. Palët kishin ngurtësuar qëndrimet dhe refuzonin negociatat. Ndërkohë, fedainët kishin krijuar në Jordani një pushtet të ngjashëm me një shtet brenda shtetit, çka dobësonte më tej pozitën e mbretit Hussein.

Konflikti shpërtheu në luftën civile jordaneze të njohur si «Shtatori i Zi», më 1970, dhe përfundoi me dëbimin e forcave fedaine nga Jordania më 1971. Husseini, me një qeveri ushtarake të sapoformuar, sulmoi organizatat e armatosura palestineze. Gjatë krizës, kërkesat e tij për mbështetje ushtarake amerikane u bashkërenduan me përgatitjet izraelite për t'i ardhur në ndihmë në rast nevoje. Kriza tregoi se shtetet arabe nuk dëshironin të tërhiqeshin në një përballje me Izraelin jashtë zgjedhjeve të tyre strategjike.

Nën drejtimin e Arafatit, OÇP-ja ishte bërë një aktor më vete, që nuk kontrollohej më nga një qeveri e vetme arabe. Megjithatë, përkrahja e përgjithshme për luftën e armatosur nuk do të thoshte pajtim ndërmjet fedainëve për strategjinë dhe taktikat. Organizata kishte fituar dukshmëri ndërkombëtare, por zgjidhja e çështjes palestineze mbetej e largët. Kriza jordaneze konsolidoi bashkëpunimin strategjik amerikan-izraelit, të shoqëruar me rritjen e ndihmës dhe të furnizimeve me armë për Izraelin. Marrëdhëniet mes dy vendeve kishin ekzistuar edhe më parë, por ky zhvillim e bënte mjedisin rajonal edhe më të pafavorshëm për realizimin e synimeve të OÇP-së.

Gjatë viteve 1970 dhe 1980, secila qeveri arabe ndiqte një strategji të vetën ndaj Izraelit dhe priste që OÇP-ja t'i përshtatej asaj. Organizata luajti rol të rëndësishëm në konfliktet rajonale dhe fitoi njohje ndërkombëtare, përfshirë njohjen arabe dhe statusin e vëzhguesit në OKB më 1974. Megjithatë, ajo mbeti jashtë shumë prej proceseve formale ndërqeveritare të luftës dhe të paqes që mund të vendosnin për një zgjidhje politike. Qeveria izraelite e cilësonte organizatë terroriste dhe nuk e pranonte si partnere negociuese. Kontaktet me Shtetet e Bashkuara zhvilloheshin kryesisht nëpërmjet kanaleve të tërthorta, të heshtura ose të fshehta dhe jo të vazhdueshme.

Gjendja ndryshoi më 1988, pasi mbreti Hussein hoqi dorë nga lidhjet juridike dhe administrative të Jordanisë me Bregun Perëndimor. Më 15 nëntor 1988, Këshilli Kombëtar Palestinez shpalli Shtetin e Palestinës, ndërsa programi politik palestinez u orientua drejt një shteti në Bregun Perëndimor dhe në Gazë. Arafati u zgjodh president i shtetit të shpallur më 31 mars 1989. Në fund të vitit 1988 ai konfirmoi pranimin nga OÇP-ja të së drejtës së Izraelit për të ekzistuar, të rezolutave 242 dhe 338 të Këshillit të Sigurimit dhe të heqjes dorë nga terrorizmi. Shtetet e Bashkuara i pranuan këto deklarime si plotësim të kushteve të tyre dhe lejuan dialogun zyrtar me OÇP-në.

Megjithatë, kur filloi procesi i paqes i Madridit më 1991, qeveria izraelite e kryeministrit Yitzhak Shamir ende refuzonte të negocionte drejtpërdrejt me OÇP-në. Sipas këtij qëndrimi, një negociim i tillë do t'u jepte legjitimitet kërkesave të saj për shtet palestinez dhe për kthimin e refugjatëve. U ndërtua një formulë përfaqësimi që të lejonte takimin pa e detyruar Izraelin të ndryshonte zyrtarisht qëndrim: një delegacion i përbashkët jordanezo-palestinez, në të cilin përfaqësuesit palestinezë vinin nga territoret e pushtuara dhe ishin përzgjedhur nga OÇP-ja. Një grup këshillimor mbështeste ekipin negociues dhe përfshinte edhe përfaqësues që Izraeli nuk i pranonte në delegacionin palestinez zyrtar, ndër ta një nga Jerusalemi Lindor; një palestinez nga diaspora u përfshi në pjesën jordaneze të përfaqësimit. Palestinezët mund të ruanin kështu një përfaqësim më të gjerë, ndërsa izraelitët mund të pohonin se nuk po negocionin me OÇP-në dhe se nuk kishin njohur Jerusalemin Lindor si pjesë të territoreve të pushtuara.

Më 1993, OÇP-ja përballej me vështirësi të rënda financiare pas Luftës së Gjirit. Mbështetja e saj për Irakun gjatë krizës së shkaktuar nga pushtimi i Kuvajtit i kishte kushtuar financimin nga shtetet e Gjirit. Në këtë periudhë, qeveria izraelite dhe OÇP-ja negociuan një marrëveshje për vetëqeverisje të kufizuar palestineze, fillimisht në Gazë dhe në qytetin e Jerikos në Bregun Perëndimor. Arafati dhe shumica e Komitetit Ekzekutiv e përkrahën propozimin, por shumë palestinezë, përfshirë pjesëtarë të ekipit negociues të mëparshëm, e kundërshtuan.

Më 9 shtator 1993, shkëmbimi i letrave të njohjes përfshiu njohjen e së drejtës së Izraelit për të ekzistuar nga OÇP-ja dhe njohjen e OÇP-së si përfaqësuese të popullit palestinez nga Izraeli; kjo nuk ishte njohje izraelite e një shteti palestinez. Më 13 shtator 1993, në Uashington, Yitzhak Rabin dhe Yasser Arafat morën pjesë në ceremoninë e nënshkrimit të Deklaratës së Parimeve, e cila hapi rrugën për zbatimin e autonomisë së kufizuar. Vetëqeverisja palestineze në Gazë dhe në Jeriko filloi, në kushte të brishta, në pranverën e vitit 1994.