Iako je uglavnom poznat po svom zalaganju za građanska prava crnačkih zajednica u Sjedinjenim Državama, također je proveo veći dio svog života govoreći o borbama naroda širom svijeta.
Naročito u posljednjim godinama svog života – nakon što se odvojio od Crne nacionalističke i separatističke Nacije islama – Malcolm je počeo komunicirati s vođama i organizatorima širom svijeta.
Tokom opsežnih putovanja po Africi i Bliskom istoku 1964. susreo je nekoliko postkolonijalnih panafričkih i panarapskih lidera, uključujući tadašnjeg egipatskog predsjednika Gamala Abdela Nasera, premijera Gane Kwamea Nkrumaha i predsjednika Gvineje Ahmeda Sekoua Tourea.
Među tim međunarodnim uzrocima bila je borba palestinskog naroda, o kojoj je Malcom bio najglasniji u posljednjih šest mjeseci svog života.
Godine 1948., u onome što je postalo poznato kao Nakba (ili katastrofa), 750.000 Palestinaca je etnički očišćeno iz svojih domova kako bi se napravilo mjesto za novostvorenu državu Izrael.
U godinama koje su uslijedile, raseljeni Palestinci su bili prisiljeni živjeti u izbjegličkim kampovima u Gazi, na Zapadnoj obali i susjednim zemljama, uključujući Jordan, Liban i Siriju.
U tom kontekstu je Malcolm dva puta posjetio Palestinu. Otišao je u Jerusalem 1959., a zatim u Gazu na dva dana u septembru 1964. godine.
Malo se zna o prvom putovanju, međutim, njegovo vrijeme provedeno u Gazi je dobro dokumentirano.
U to vrijeme, pojas Gaze je bio pod kontrolom Egipta (koji je preuzeo enklavu 1948.) i stoga je putovanje između dvije teritorije bilo relativno lagano.
Prema njegovim putnim dnevnicima, Malcolm je posjetio izbjeglički kamp Khan Younis, koji je stvoren 1949. nakon Nakbe za smještaj ljudi raseljenih iz drugih dijelova Palestine.
Također je posjetio lokalnu bolnicu i večerao s vjerskim vođama u Gazi.
Kasnije uveče se susreo sa poznatim palestinskim pjesnikom Harunom Hashemom Rašidom, koji mu je opisao kako je za dlaku izbjegao masakr u Khan Younisu 1956. godine.
Tokom masakra, koji se dogodio u jednosedmičnom ratu koji je postao poznat kao Suecka kriza, izraelske snage su išle od kuće do kuće i pogubili ukupno 275 Palestinaca (od kojih su većina bili civili) u južnoj Gazi.
Rašid je recitovao pjesmu o palestinskim izbjeglicama koje se vraćaju u svoje zemlje, koju je Malcolm prepisao u svoj dnevnik, prema radu Hamzaha Baiga o Malcolmu i Palestini iz 2019.
“U 20:25 krenuli smo prema džamiji da klanjamo sa nekoliko vjerskih vođa. Duh vjere u Boga je bio jak”, napisao je Malcolm u svom dnevniku.
Kako bi završio putovanje, posjetio je zgradu parlamenta u Gazi i održao konferenciju za novinare s raznim lokalnim ličnostima.
„Tamo su me obasipali poklonima“, napisao je, uključujući i sliku Asuanske visoke brane skinute sa zida u zgradi parlamenta.
Napustio je Gazu 6. septembra u podne i vratio se u Kairo.
Dana 15. septembra, u kairskom hotelu Shepheard's, Malcolm se sastao sa članovima novoformirane Palestinske oslobodilačke organizacije (PLO), uključujući Ahmada al-Shukeirija, prvog predsjednika grupe.
Nekoliko dana nakon puta u Gazu, Malcolm je napisao svoj najopsežniji članak o palestinskoj stvari.
Dana 17. septembra 1964. objavio je esej “Cionistička logika” u kairskim novinama, Egyptian Gazette.
U tekstu, on opisuje cionizam kao “novi oblik kolonijalizma” koji se čini “dobronamjernim” i “filantropskim”. On je upozorio da Izrael iskorištava nove nezavisne afričke zemlje u ekonomskim poteškoćama kroz ekonomsku pomoć.
On je takođe optužio Zapad da strateški pokušava da podeli Afrikance i Azijate kroz stvaranje države Izrael.
„Evropski imperijalisti koji se stalno nameću mudro su smjestili Izrael tamo gdje je mogao geografski podijeliti arapski svijet, infiltrirati se i posijati sjeme razdora među afričkim vođama i također podijeliti Afrikance protiv Azijata“, napisao je.
„Stalno nizak životni standard u arapskom svijetu vješto su iskoristili cionistički propagandisti kako bi Afrikancima ukazalo da arapski lideri nisu intelektualno ili tehnički osposobljeni za podizanje životnog standarda svog naroda.
„Na taj način, indirektno podstičući Afrikance da se okrenu od Arapa prema Izraelcima radi nastavnika i tehničke pomoći.“
U završnom dijelu eseja doveo je u pitanje opravdanost Izraela za državu zasnovanu na “obećanoj zemlji”.
“Ako je istinita ‘vjerska’ tvrdnja cionista da ih je njihov mesija trebao odvesti u obećanu zemlju, a sadašnja izraelska okupacija arapske Palestine je ispunjenje tog proročanstva: gdje je njihov mesija[?]”, upitao je on. .
Zatim je napravio poređenje s muslimanskom vladavinom nad Španijom, i da li će taj period dati muslimanima pravo da napadnu Iberiju u današnje vrijeme.
“Prije samo hiljadu godina, Mauri su živjeli u Španiji. Da li bi ovo današnjim Maurima dalo zakonsko i moralno pravo da napadnu Iberijsko poluostrvo, protjeraju njegove španske građane, a zatim uspostave novu marokansku naciju… gdje je Španija nekada, kao što su evropski cionisti učinili našoj arapskoj braći i sestrama u Palestini?”
On zaključuje da izraelski argument da opravda svoju “sadašnju okupaciju arapske Palestine nema inteligentnu ili pravnu osnovu u historiji”.
Malcolm je ubijen 21. februara 1965. godine, nakon što je upucan više puta dok je držao govor u dvorani Audubon na Manhattanu.