W latach 1974–1980 siedziba organizacji znajdowała się w Bagdadzie, a jej poczynania były w dużym stopniu kierowane przez Irak. Została wydalona z Iraku w 1980 roku – wpływ na to miała wojna iracko-irańska, w której trakcie Irak dążył do poprawy stosunków z Zachodem oraz spór między Abu Nidalem a Irakiem dotyczący niezależności organizacjiTerroryzm od Asasynów do Osamy bin Ladena s. 84-85. Do 1985 roku jej siedziba znajdowała się w Syrii, a od 1985 roku w Libii. W okresie rezydowania jej przywódców w Libii uchodziła za wykonawcę polityki Mu’ammara al-Kaddafiego. W 1987 roku organizacja przeszła proces wewnętrznej reorganizacji: rozpoczęła działalność w południowym Libanie, gdzie rekrutowała nowych członków spośród społeczności palestyńskich uchodźców, tworzyła struktury milicyjne i włączyła się w działalność polityczno-społeczną. W 1989 roku około 150 członków organizacji, w tym wielu jej dowódców potępiło Libię i wyjechało do Sudanu. Od 1992 roku Libia usiłowała wymusić na grupie wstrzymanie się od działalności terrorystycznej. We wczesnych latach 90. stronnicy Abu Nidala bezskutecznie usiłowali przejąć kontrolę nad obozem dla palestyńskich uchodźców w Sydonie, a w 1994 roku zaangażowali się w zamach na sekretarza ambasady jordańskiej w Bejrucie.