Jugoslavija je u drugoj polovini 20. veka igrala iznenađujuće važnu ulogu u afirmaciji palestinskog pitanja na međunarodnoj sceni. U središtu tog savezništva bio je lični odnos Josipa Broza Tita i Jasera Arafata – prijateljstvo koje je nadilazilo protokolarne susrete i pretvorilo Beograd u jedno od ključnih diplomatskih uporišta palestinske borbe.
Jugoslavija je 1948. godine bila među prvim državama koje su priznale novoosnovani Izrael, delimično pod uticajem Moskve. Beograd je tada učestvovao i u snabdevanju izraelske vojske oružjem. Međutim, već krajem četrdesetih, nakon sukoba Tita i Staljina, spoljnopolitički kurs Jugoslavije počeo je da se menja.
Kako beleži slovenački istoričar Žiga Smolič, značajan zaokret ka podršci Arapima i Palestincima nastupio je sredinom šezdesetih. Od 1965. jugoslovenska diplomatija sve otvorenije ističe palestinsko pitanje u Ujedinjenim nacijama. Prekretnica je bio rat 1967. godine, nakon kojeg je Jugoslavija prekinula odnose s Izraelom i poslala pomoć arapskim zemljama i palestinskim izbeglicama, pisao je Radio Sarajevo.

Posebnu dimenziju jugoslovensko-palestinskim odnosima dao je lični odnos Josipa Broza Tita i Jasera Arafata, lidera Palestinske oslobodilačke organizacije (PLO). Arafat je Jugoslaviju posetio više puta, a prvi susret s Titom imao je u Alžiru 1973. godine. On je Tita opisivao kao „najiskrenijeg prijatelja palestinskog naroda“.
Na Brdu kod Kranja 1974. Arafat je izjavio: „Kada sam prvi put došao u Jugoslaviju, Naser mi je rekao da idem da posetim najvećeg i najodanijeg prijatelja Arapa.“ Njegove reči ostale su trajno zabeležene u arhivima Muzeja istorije Jugoslavije.
Raif Dizdarević, jedan od ključnih jugoslovenskih diplomata i kasniji predsednik Predsedništva SFRJ, svedočio je da se sa Arafatom sastajao „bezbroj puta“. On je opisao kako su susreti stvarali atmosferu ličnog poverenja i iskrene saradnje: „SFR Jugoslavija je među prvima priznala PLO kao jedinog legitimnog predstavnika palestinskog naroda i angažovala se da to učine i druge zemlje.“
Tito je koristio i platformu Pokreta nesvrstanih kako bi osnažio legitimitet palestinske borbe. Jugoslavija je aktivno lobirala da se pitanje Palestine stalno nalazi na dnevnom redu međunarodnih foruma. Beograd je bio važna diplomatska stanica za Palestince, mesto gde su tražili razumevanje, savet i podršku.
Arafat je u jednom razgovoru sa Dizdarevićem 1986. u Dubrovniku rekao: „Kad nam situacija postaje sve teža, mi kažemo: očigledno je da valja ići na razgovore u Beograd. Beograd je bio i ostao naša najvažnija stanica, čak i za naše interne probleme.“

Tito nije davao samo deklarativnu podršku, već je Arafatu pružao i političke savete. U Beogradu 1974. upozorio ga je na „opasnost balkanizacije oslobodilačke organizacije“ i rizik od američko-izraelskih manipulacija unutar arapskog sveta.
Dizdarević je beležio da Arafat nikada nije bio pobornik slepog terora. „U svim razgovorima isticao je da bez oružane borbe nema pregovora, ali je uvek tragao i za političkim rešenjima“, napisao je bivši predsednik Predsedništva SFRJ. Arafat je 1985. u Kairu objavio deklaraciju kojom se Palestinci odriču terorizma, uz poruku da se borba mora voditi protiv izraelske okupacije, a ne nad civilima.
Posle Titove smrti 1980. Arafat je došao u Beograd da oda poštu, svestan koliko je Jugoslavija značila za međunarodnu afirmaciju Palestine.
Jugoslavija je priznala Državu Palestinu 1988. godine i sa njom uspostavila pune diplomatske odnose 1989.
Tokom jugoslovenskih ratova 1990-ih, Palestina je je priznala Saveznu Republiku Jugoslaviju (tada Srbiju i Crnu Goru) i sve ostale bivše Jugoslavije republike.