Прямым результатом встречи было то, что Арафат попросил Таккедина сделать для Вазира и Халафа фальшивые студенческие документы и включить их в делегацию. Таккедин согласился, потому что имел на Арафата серьезные виды. Свои планы он открыл ему перед самым отлетом. Он признался, что давно принадлежит к «Мусульманским братьям», недоволен секулярно-социалистическим курсом Насера и разделяет гнев и возмущение Синайским поражением. Ихван готовится к свержению Насера и для этого установил связи с иностранной разведкой. Задача Арафата — встретиться в Праге с представителями этой разведки, которые передадут ему дальнейшие распоряжения.
Арафат напрасно ждал обещанных агентов. Они не вышли на связь. Планы, о которых рассказывал Таккедин, рухнули. На митинге в Каире люди Ихвана совершили покушение на Насера, и тот обрушил на Ихван жестокие репрессии. «Мусульманские братья» были объявлены вне закона. По всему Египту шли аресты, и представителям египетского посольства в Праге было дано указание задержать Арафата и его друзей. Обманув преследователей, Арафат, Халаф и Вазир покинули Прагу. Меняя поезда, они пробрались в Штутгарт, где у Халафа были друзья среди тамошних палестинских студентов.
В Штутгарте они пробыли всего три месяца. Здешние палестинцы были настроены, в основном, панарабистски и социалистически, призывы Арафата их не увлекли. Выручило объявление в газете. В Кувейте требовались инженеры-строители. У Арафата был диплом, наскоро изготовленный в отделе Таккедина перед отлетом в Прагу. Он представил его в кувейтское консульство и вскоре оказался в самолете, который следовал рейсом на Персидский залив.
Кувейт в те годы переживал строительную лихорадку. Арафат получил назначение в министерство общественных работ, где в его обязанности входило проверять проекты, предложенные заграничными компаниями, и решать, кому из них предоставлять лицензии. Он быстро сообразил, как можно на этом заработать. На свои небольшие средства он арендовал небольшой грузовик, написал на его бортах «Строительная компания свободной Палестины, владелец Я. Арафат» и от имени министерства сам себе выдал лицензию на все работы по строительству водопровода для домов палестинских рабочих на берегу залива. Деньги, выделенные под лицензию, он использовал для найма рабочих. Прежде всего были наняты Вазир и Халаф, все еще находившиеся в Штутгарте. Затем в компании появился молодой палестинец из Назарета Фарук Кадуми, бывший участник организованных сирийцами антиизральских диверсий. В начале 1959 года к маленькой группе присоединился бывший руководитель штутгартских палестинцев аль-Хассан, и еще несколько беженцев, живших в Кувейте. Вазир и Халаф были вызваны из Штутгарта. Они привезли с собой новые идеи. Палестина, утверждали qhh, должна быть освобождена революционными методами партизанской борьбы, подобной той, которую ведут революционеры в Алжире, Китае и Вьетнаме. Штутгартцы успели установить тесные связи с алжирским Фронтом национального освобождения, который обещал палестинцам свою поддержку. После недолгих возражений Арафат присоединился к рассуждениям штутгартцев. Группа — в ней состояло тогда около 20 человек — решила создать боевую организацию наподобие алжирской. Долго спорили о названии, наконец остановились на «Движении за освобождение Палестины». Получившийся акроним «Хатаф» перевернули в «Фатах», Фатх. Название понравилось. Оно было принято. На первом же заседании — оно состоялось в середине лета 1959 года — решили отправить Халафа и Хассана обратно в Германию — налаживать связи со студентами и алжирцами.
Новорожденный Фатх мало чем отличался от десятков других молодежных групп, в то время возникавших и исчезавших в палестинской диаспоре. Он тоже был бы обречен на исчезновение, если бы не те новые идеи, которые провозгласил с первых же шагов. Идеи эти состояли в том, что до сих пор палестинцы слишком полагались на помощь арабских лидеров. Пришло время осознать, что освободить родину могут лишь сами палестинцы и прежде всего — палестинская молодежь.
В те годы термины «национальное освобождение» и «национальное самоопределение» были на устах у всех. Они пришлись по вкусу и палестинской молодежи, которая не имела никакой своей идеологии. Особенно увлеклись ими палестинские студенты в Европе, уже знакомые с риторикой других национальных движений. Халаф и Хассан успешно вербовали все новых и новых членов в европейские ячейки Фатха.
С самого начала политического пути несколько особенностей отличали Арафата. Первой из них было искусное использование лжи, обмана и демагогии. Урок этот был преподан ему в детстве — дядей Юсуфом, отцом, учителем, Абделькабиром и другими. Кое-кто, столкнувшись с ложью в детстве, становится нетерпимым к ней на всю жизнь. Другие смиряются с ней, как с житейской неизбежностью. Третьи осознают, что она является одним из лучших орудий манипулирования людьми и массами. Арафат принадлежал к этим последним.