W lutym 1976 roku spotkał się w Adenie z Wadim Haddadem. Palestyńczyk poinformował go o usunięciu z szeregów LFWP. Miało to być karą za niewykonanie rozkazu likwidacji ministrów Iranu i Arabii Saudyjskiej w trakcie ataku na szczyt OPEC. Od tego czasu terrorysta działał na własną rękę i pracował jako najemnik dla rządów państw arabskich i bloku wschodniego.
Przez pierwsze dwa lata od zamachu na szczyt OPEC ukrywał się. Przebywał m.in. w Jugosławii (gdzie został na krótko aresztowany), Jemenie Południowym i Syrii. Dopiero w 1977 roku zamieszkał na stałe w Bagdadzie. Podczas pobytu w Iraku osobiście poznał Saddama Husajna.
W marcu 1978 roku zmarł Haddad, a „Szakal” uznał, że to odpowiedni moment na utworzenie nowej grupy terrorystycznej. Do nowej formacji zwerbował grupę aktywistów LFWP oraz kilku Szwajcarów i Niemców. W 1979 roku ogłoszono istnienie Organizacji na rzecz Arabskiej Walki Zbrojnej. W tym samym czasie poślubił Magdalenę Kopp będącą terrorystką zachodnioniemieckich Komórek Rewolucyjnych.