В Москве Мильке учился в Международной ленинской школе, после ее окончания даже преподавал в ней. Когда в Испании произошел фашистский переворот, он без колебаний отправился туда добровольцем, взяв псевдоним Фриц Ляйснер. В составе сил сопротивления фашистскому генералу Франко капитан Мильке получил должность начальника оперативного отдела бригады, а затем инструктора 11-й интернациональной бригады и стал начальником ее штаба. После тяжелых боев и не менее тяжелого поражения испанских коммунистов Мильке нелегально перебрался в Бельгию и там устроился в редакцию одной из левых газет.
С началом гитлеровского вторжения в Бельгию он бежал во Францию, где влился в ряды французского Сопротивления. Биография совершенно непростого человека: герой Сопротивления, доброволец, красный журналист и профессиональный революционер — с таким послужным списком он легко вписался в созданную после войны Германскую Демократическую Республику. И уже став главой всесильной Штази, изо всех сил помогал молодым революционерам, в то же время железной рукой пресекая попытки скомпрометировать или подставить ГДР.
Впервые Штази серьезно обратила внимание на палестинские движения в 1972 году, когда члены группы «Черный сентябрь» захватили в заложники израильских спортсменов, приехавших выступить на Олимпийских играх в Мюнхене. По личному распоряжению главы ГДР Эриха Хонеккера Мильке установил контакт с революционерами из палестинского лагеря. Выполнение этой задачи было поручено главе разведывательного управления, входящего в состав МГБ, Маркусу Вольфу.
В книге «Тайная война Карлоса Шакала» Джон Фоллейн приводит интервью с Вольфом, в котором он рассказывает, что Хонеккер встретился с Ясиром Арафатом еще в 1972 году:
«Позднее, в Москве, мой заместитель, ответственный за связи с арабскими странами, переговорил с Арафатом и сообщил ему, что мы готовы предоставить ему поддержку при условии, что территория ГДР не будет использована как опорный пункт для проведения террористических акций. Разумеется, было бы наивным полагать, что это условие будет выполняться. Мы также дали понять Арафату, что очень огорчены акцией в Мюнхене».
Кроме того, Вольф сказал, что обе стороны выиграли от дальнейшего сотрудничества: палестинские офицеры обучались военному делу и диверсионной работе в Восточной Германии, получали оружие и иную помощь от Штази, а Штази, в свою очередь, получала ценную информацию о ситуации в арабских странах, Израиле и готовящихся атаках революционеров на объекты западного лагеря.
В 1975 году генерал Мильке дал распоряжение создать в МГБ новый департамент, получивший название «подразделение XXII». Этот департамент занимался контролем и противодействием терроризму на территории ГДР, но на самом деле подразделение XXII отвечало за связи с дружественными революционерами, в том числе с сопротивлением Палестины. Контртерроризм был направлен прежде всего на боевиков, замышляющих акции против СССР, Восточного блока и стран третьего мира. Остальные — вэлкам, добро пожаловать.
Революционеры же получали от офицеров Штази права транзита и проживания взамен на лояльное отношение к органам власти Восточной Германии. Члены западногерманского RAF были частыми гостями ГДР, пересиживая там после проведения очередных операций. Теперь сюда стали стекаться и представители многих других международных повстанческих движений.
Итак, в конце марта 1979 года в Восточный Берлин приезжает собственной персоной Карлос, как всегда помпезно и почти с фанфарами, остановившись в дорогой гостинице «Штадт Берлин» (ныне «Форум»). Там он зарегистрировался под именем йеменского дипломата Ахмеда Али Фаваза. Сам дипломат пока подчеркнуто держал дистанцию, однако его помощник Йоханнес Вайнрих вовсю ездил на встречи с чинами восточноевропейской разведки. Что хотел Карлос от ГДР? Согласно рассекреченному ныне рапорту генерала Ирмлера, Йоханнес Вайнрих так в общих чертах пояснил интересы шефа в Восточном Берлине:
«Создать базы в столице ФРГ и заслать агентов из группы Карлоса с заданиями в Западную Германию и Западный Берлин; установить постоянные контакты с Йеменом, Ираком и Ливийской Республикой, а также с Народным фронтом в столице Восточной Германии; добывать оружие, взрывчатку, деньги и информацию… осуществлять вооруженные нападения, направленные против конкретных лиц, с целью противодействия империалистической политике Соединенных Штатов Америки и сионизма; возобновить контакты с анархо-повстанческими силами в Западной Германии и Западном Берлине. К тому же группа хотела бы получить гарантии того, что посольства Восточной Германии и Советского Союза в Дамаске помогут организовать ей опорные пункты в Сирии» (отчет Штази от 1979 года, опубликованный в книге «Тайная война Карлоса Шакала»).
В Штази отметили и идеологическую направленность Карлоса, который борется против империализма, расизма, колониализма и других реакционных сил: