La politica estera del governo Craxi si incentrò sul tradizionale atlantismo, ma molti sforzi vennero fatti per mantenere buone relazioni con i paesi bagnati dal Mediterraneo, quindi i paesi arabi. Per questo era fondamentale mantenere buone relazioni con Arafat, leader dell'Olp, e cercare una soluzione al problema palestinese. Nel novembre 1984 Craxi e Andreotti si recarono in visita in Egitto, dove il presidente Mubarak stava tentando di mediare per la questione israelo-palestinese e per il miglioramento delle relazioni tra l’Olp e i paesi arabi. Tra i paesi europei, era sull’Italia che il presidente egiziano mostrava di voler fare speciale affidamento. Nel dicembre invece incontrarono Arafat, spingendolo a rendersi disponibile alla formazione di un assetto federale o confederale giordano-palestinese, ma le sue risposte furono ambigue. Tra il re di Giordania Hussein ed Arafat ci fu un accordo sulla futura unione giordano-palestinese, ma la Cisgiordania era ancora occupata da Israele, conquistata a seguito della Guerra dei sei giorni del 1967, per cui non si poteva prescindere dalle decisioni dello stato ebraico. A febbraio venne ricevuto a Roma il capo del governo israeliano Peres (la prima volta a Roma per un premier israeliano), che si mostrava favorevole a discutere con giordani e palestinesi, ma non con l’Olp, considerata un’organizzazione terroristica da Tel Aviv. Al di là di questo, i rapporti tra la Giordania e l’Olp peggiorarono progressivamente, rendendo vani gli sforzi fatti dal governo Craxi.

Il governo italiano, con la collaborazione del governo egiziano e di Arafat, riuscì anche a gestire le trattative con i sequestratori (appartenenti a un ramo ribelle dell'Olp) della nave da crociera Achille Lauro, che si arresero. Gli egiziani avevano accettato di partecipare al compromesso che avrebbe posto fine al dirottamento a condizione che i quattro terroristi, considerati responsabili, venissero trasportati in Tunisia (sede dell'Olp) a bordo di un aereo egiziano accompagnati da Abu Abbas, figura politica vicina ad Arafat e mediatore dell’accordo, come garante del fatto che essi sarebbero stati sottoposti, sotto l’autorità di Arafat, a regolare processo per aver compiuto un attentato che comprometteva i negoziati, allora in corso, per una soluzione della questione palestinese. Gli accordi vennero rispettati al costo di una crisi diplomatica tra Roma e Washington, che stava per sfociare in un conflitto a fuoco tra militari italiani e americani nella base militare di Sigonella.