В июне 1960 года советские эмиссары побывали в гостях у своих восточно-германских союзников и потребовали от них участия в «политической деятельности» государств третьего мира. Руководствуясь главным образом соображениями экономии, русские закрепили за ГДР Ближний Восток и Африку. Позднее они добавили к этому списку Латинскую Америку. Вальтер Ульбрихт, глава СЕПГ и правительства ГДР, в прошлом теснс сотрудничавший с советскими органами госбезопасности, взялся за дело с великим усердием. Ульбрихт и его Политбюро увидели в предложена СССР прекрасную возможность установить экономические связи и добиться признания ГДР хотя бы государствами третьего мира. Восточная Германия находилась в изоляции, причиной которой являлась боннская доктрина Галльштейна, призывавшая к разрыву дипломатических отношений с любой страной, официально признавшей ГДР. В конце 60-х годов ситуация изменилась, когда западногерманский канцлер Вилли Бранд провозгласил новую политику сближения с Восточной Епропой, получившую название «Остнолнтик» — восточной политики.

Контакты, устанавливаемые в разнимающихся странах, имели первоначально подпольный характер. Главным образом это определялось специфической деятельностью министерства госбезопасности ГДР. У себя на родине, в ГДР, офицеры МГБ готовили кадры для нелегальной работы — коммунистов, а также прочих лиц из числа враждебно относившихся к Западу, особенно Соединенным Штатам и Израилю. Подобные контакты участились настолько, что Политбюро СЕПГ Решило создать особое учреждение для дальнейшего осуществления нелегальной «учебы».

Герман Аксен, возглавлявший международный отдел Политбюро, стал главным исполнителем этого дела. Он нашел себе для этой цели прекрасного партнера в нще Эриха Мильке, поскольку для этой цели идеально подходила школа МГБ, располагавшаяся в Потсдаме-Эйхе. По приказу Мильке было создано управление внешних сношений. Размещалось оно не на территории школы МГБ, а в строго засекреченном местечке близ Потсдама, за пределами Восточного Берлина. К конце 1969 года в этом управлении открылось новое отделение, и в течение нескольких лет его «ученики» были главным образом члены арафатовской Организации Освобождения Палестины (ООП). Сотни людей прошли подготовку по разведывательным и контрразведывательным операциям. Необходимости учить их обращению с оружием, взрывчатыми веществами или приемами рукопашного боя не было. На тайной «инаугурационной» церемонии открытия этого управления Мильке сказал: «Эти люди уже знают, как надо воевать. Это они могут нас кое-чему научить в деле обращения со взрывчаткой».

В апреле 1971 года увлеченность Мильке своей работой на посту главы тайной полиции достигло масштабов, достойных настоящего трудоголика: кроме вопросов внутренней безопасности ГДР и внешней разведки, а также поддержки отношений с международными террористами, он еще и контролировал важнейшие, события внутрипартийной (СЕПГ) жизни. Он давно уже понял, что Москву начинает все больше беспокоить буйное поведение Вальтера Ульбрихта, даже несмотря на энергичные действия последнего в оказании помощи национально-освободительным движениям. Когда Ульбрихта отправили в отставку, русские решили, что его место должен занять Эрих Хонеккер. Хонеккер был секретарем ЦК СЕПГ по вопросам безопасности и, следовательно, — товарищем Эриха Мильке по оружию. Мильке сумел сблизиться с Хонеккером, не ущемляя самолюбия Ульбрихта. Таким образом, когда из Страны Советов поступил соответствующий сигнал, было вполне естественно, что глава Штази, поддержал Хонеккера, выступавшего против Вальтера Ульбрихта. В награду за это Хонеккер предоставил Мильке пост в самом влиятельном партийном органе — Политбюро. С тех пор он стал пользоваться неограниченной и никем не контролируемой властью в руководстве министерства госбезопасности ГДР, — до тех, правда, пределов, пока это не мешало коренным интересам СЕПГ. В том, что касалось отношений ГДР с террористами, Хонеккер являлся уступчивым руководителем, который никогда не отказывал Мильке в его просьбах и неизменно следовал советам министра госбезопасности.

Весной 1974 года, когда Мильке вернулся с одной из своих многочисленных консультаций с Москвой, он незамедлительно отдал приказ о созыве большого совещания руководителей главного управления МГБ. Оно состоялось в Лихтенберге — одном из районов Восточного Берлина, в импозантном здании на холме, в самом центре огромного комплекса министерства госбезопасности. Сотрудники госбезопасности называли это местечко Фельдхеррнхюгель (холм фельдмаршала), потому что здесь Мильке отдавал свои распоряжения и манере верховного главнокомандующего. Он открыл совещание своим обычным призывом к бдительности. После того Мильке сообщил, что «наши друзья» (он всегда называл так русских) в очередной раз попросили ГДР укрепить отношения с зарубежными государствами и особенно со странами Ближнего Востока.

Лишь немногим из присутствующих было известно о том, что МГБ уже занимается обучением арабских террористов в тайных лагерях неподалеку от Берлина. Но те, кто хотел узнать немного больше положенного, ироде полковника Райнера Виганда, сразу поняли, что главная тема совещания — помощь террористам, хотя сам Мильке этого слова не употребил. В своем выступлении глава МГБ упомянул о том, что вопрос мирового господства — победа в противостоянии капитализма и социализма — будет определяться позицией стран третьего мира.

Мильке сообщил присутствующим, что арабский мир особо пристально следит за исходом этой эпической схватки и что «в борьбе с империализмом решительный вклад в дело победы социализма сделает тот, кто будет контролировать разведывательные организации этих стран».

Первый шаг в деле укрепления предпринятых Советским Союзом усилий Мильке сделал через два месяца после совещания в Фельдхеррнхюгеле в отношении Народной Республики Южный Йемен — ближайшего идеологического союзника СССР в арабском мире.

Столица Йемена Аден с ее великолепной базой имеет важное стратегическое значение в качестве базы для морских операций СССР в Индийском океане. Долгие годы КГБ держал там свой контингент, однако сотрудникам могущественной советской организации приходилось в этой стране нелегко. Как выяснил КГБ, внедрение в ряды йеменской марксистской партии и работа с охранниками правительства и местными разведчиками было весьма нелегким делом из-за нескольких здешних интриг. Это было еще одной причиной того, что Москва попросила МГБ ГДР помочь ей в йеменских делах. 3-й отдел главного управления «А» получил команду «разрабатывать йеменское направление». Этот отдел отвечал за создание легальных резидентур в странах, дипломатически признавших ГДР, и в среде участников «освободительных движений». Полковник Фидлер начал работать в Адене, имея в своем подчинении лишь 60 офицеров, и добился там столь значительного успеха, что контингент сотрудников Штази быстро увеличился до ста человек.

Как и их предшественники из КГБ, восточные немцы решили, что йеменское министерство государственной безопасности отличается крайне неудовлетворительной организацией и большой уязвимостью, способствующей внедрению в его ряды агентов вражеских разведслужб.

Первоочередной задачей полковника Фидлера была перестройка структуры министерства в соответствии со структурой Штази и внедрение его подчиненных — восточных немцев — в каждый из отделов в качестве «инструкторов». Таким образом восточные немцы добились определенного контроля и доступа ко всем оперативным делам, включая подготовку и помощь террористам: Южный Йемен был главной тренировочной площадкой для различных международных террористических организаций, которые получали материально-техническую поддержку со стороны йеменской разведки. Благодаря своему привилегированному положению сотрудникам Штази удалось составить обширные досье на террористов и их подпольную деятельность. Деятельность Штази в Южном Йемене занимала, пожалуй, главнейшее место в ее связях с международным терроризмом за пределами ГДР.