Попытки Саддама интегрировать Ирак в общую арабскую политику отразились также в его подходе к палестинской проблеме. Уже во время встречи на высшем уровне в Рабате в октябре 1974 года Ирак отказался от своей упорной приверженности к вооруженной борьбе против Израиля и принял поэтапную стратегию, которая предусматривала образование небольшого палестинского государства на Западном берегу и в секторе Газа как промежуточную стадию «конечного освобождения Палестины». Поддержав это изменение в политике, Саддам надеялся убить двух зайцев: представить Ирак умеренным консервативным арабским режимом и сократить военное участие Ирака в деле освобождения Палестины. Как он честно признался, освобождение Палестины военными средствами будет невозможно, пока не построен «сильный в научном, экономическом и военном отношении Ирак».
Неудивительно, что этот подход не удовлетворил ООП, которая давно уже имела зуб на Ирак за то, что он не пришел ей на помощь во время «Черного сентября» 1970 года. Багдад, со своей стороны, ответил поддержкой экстремистских группировок внутри палестинского движения, таких как печально знаменитая Сабри-эль-Банна, больше известная по боевому прозвищу своего лидера (Абу Нидаль), которая действовала, дислоцировавшись на территории Ирака. Хотя Ирак выступал на стороне ООП против сирийской военной интервенции в Ливан в 1976 году (первоначально направленной в поддержку христиан против палестинцев), его политика была мотивирована больше желанием подорвать сирийские позиции, чем сочувствием к положению ООП. Отношения между Ираком, аль-Фатах, самой крупной группировкой внутри ООП, и собственной организацией Арафата, достигли низшей точки в начале 1977 года. Не прекращая своих террористических акций против Ирака и Израиля, аль-Фатах закрыла свои организации в Багдаде и изъяла оттуда свои финансовые фонды. Палестинская организация распространяла брошюры, характеризующие Саддама как профессионального убийцу, и нападала на Ирак за то, что он не входил в «прогрессивный» лагерь, выступающий против мирных переговоров Анвара Садата с Израилем.
Багдад ответил обвинением аль-Фатах в «клевете против иракской партии Баас и правительства».
Но, как это часто бывает, перспектива разрядки напряженности между Египтом и Израилем оказалась достаточной, чтобы еще раз сблизить два лагеря. Их антагонизм внезапно сошел на нет в конце 1978 года, когда Хусейн, пытаясь играть видную роль во всеарабских усилиях заблокировать стремление Анвара Садата к миру с Израилем, быстро двинулся к примирению с аль-Фатах и вообще с ООП. Саддам и Арафат встретились в Багдаде в ноябре 1978 и еще раз в марте 1979 года, и Багдад помешал действиям Абу Нидаля против ООП.