Москва одобрительно отнеслась ко все более энергичным попыткам Арафата завоевать международное признание. В 1979 году он был приглашен на заседание Социнтерна в Вене и оттуда же начал успешное дипломатическое наступление. К 1980 году страны Европейского Сообщества, но не Соединенные Штаты, согласились, что ООП должна участвовать в мирных переговорах на Ближнем Востоке. Министр иностранных дел Великобритании лорд Каррингтон заявил: «ООП как таковая не является террористической организацией».
Арафат удачно вбил клин между Соединенными Штатами и их европейскими союзниками, что значительно повысило его ставки в Москве. В 1981 году Брежнев дал ООП официальный дипломатический статус. Однако, когда в 1982 году Израиль напал на базы ООП в Ливане, Арафат упрекал Москву за невмешательство.
В то же время, Московский центр все больше беспокоили сообщения о тайных встречах между лидерами ООП и американскими официальными лицами. Подозревалось, что Арафат уступил западному нажиму и сам решил исключить Советский Союз из ближневосточного урегулирования. Естественно, в Москве это вызвало большое неудовольствие. Гордиевского поразил тот факт, что в официальных советских сообщениях Арафата больше не называли товарищем. Это был явный знак того, что в глазах Москвы он превратился из социалистического союзника в буржуазного националиста. На совещании в лондонском посольстве в 1983 году, на котором присутствовал и Гордиевский, начальник управления стран Ближнего Востока МИДа Олег Алексеевич Гриневский сообщил советским дипломатам и офицерам КГБ, что Москва больше не верит Арафату. Высказывалась надежда, что в конечном итоге на смену ему придут марксистские и прогрессивные члены ООП. Тем не менее только Арафат был способен удержать ООП от распада, и поэтому Советский Союз продолжит оказывать ему умеренную официальную поддержку.
Советская ближневосточная политика при Брежневе была направлена на создание «антиимпериалистического блока» против Израиля и его американского союзника. Почти все десятилетие семидесятых годов Москва поддерживала очень тесные связи с Ираком, с которым в 1972 году был подписан Договор о дружбе и сотрудничестве. Вскоре после подписания договора и КГБ заключил соглашение о сотрудничестве с иракской разведкой. К 1977 году это сотрудничество стало настолько тесным, что Ирак превратился в единственную некоммунистическую страну, где советский шпионаж был прекращен. Центр принял беспрецедентное решение и отдал соответствующее указание своим резидентурам прекратить разведывательные операции против объектов Ирака. Все связи с иракскими агентами должны были стать «официальными контактами». Если советско-иракские отношения ухудшатся, то связи необходимо было возобновить. Особые связи с иракской разведкой почти прекратились после апреля 1979 года, когда иракский диктатор — генерал Саддам Хусейн — отправил в тюрьму или казнил большое число иракских коммунистов. Резидентурам КГБ был отдан приказ немедленно восстановить связи с бывшими иракскими агентами. Советско-иракские отношения еще более осложнились, когда в сентябре 1980 года Саддам Хусейн напал на Иран и началась война в Персидском заливе. После некоторых раздумий Москва решила оказать Ираку тайную поддержку. Ведущий эксперт по внешней политике в Секретариате ЦК КПСС, а в дальнейшем и личный советник Горбачева Николай Владимирович Шишлин заверил Гордиевского, что путь поставки Ираку вооружений был так хитро замаскирован, что выявить его было практически невозможно.
Москва стремилась вовлечь в антиимпериалистический ближневосточный блок и соседа и соперника Ирака — Сирию, которая получала еще больше советского оружия, чем Ирак. В своих мемуарах Громыко так воспевает сирийского лидера Хафеза Асада: «Сильный и дальновидный лидер, пользующийся уважением как в арабском мире, так и за его пределами. Он всегда понимал всю важность советско-арабской дружбы… Хорошо одетый, с тенью улыбки, иногда скользившей по губам, он выглядел немного неприметно, но на самом деле Асад был человеком очень выдержанным, внутри его чувствовалась сильная пружина.»
В частных беседах Гордиевский часто слышал неодобрительные отзывы об Асаде как в Центре, так и в Международном отделе ЦК КПСС. Его называли мелкобуржуазным шовинистом и эгоманьяком. Центр с гораздо большим доверием относился к руководителям разведслужбы Асада, с которыми в семидесятые годы были установлены полезные и тесные связи.
В 1979 году в ПГУ был образован новый 20 отдел для контроля связей с «прогрессивными разведками» за пределами советского блока, например, в Сирии. Помимо резидента КГБ в Дамаске, которого сирийское правительство не знало, там же в советском посольстве работал и представитель 20 отдела, осуществлявший связи с сирийской разведкой и организовывавший направление сирийских офицеров для подготовки в Москву. Хотя советская и сирийская разведка не делились друг с другом наиболее секретными сведениями, несколько раз сирийцы передавали в Москву интересные материалы о западных службах. Асад также разрешил 16 управлению КГБ проводить некоторые операции на своих одиннадцати станциях электронной разведки.
Самым близким идеологическим союзником СССР в арабском мире была Народная Демократическая Республика Йемен (НДРЙ), образованная в 1967 году после ухода англичан из Адена. Тем не менее, на памяти Гордиевского КГБ всегда рассматривал Южный Йемен как источник постоянных проблем. Главным занятием огромной резидентуры КГБ в Адене было наблюдение за внутренними интригами и борьбой за власть в Йеменской социалистической партии. Контролировать эти процессы было почти невозможно. В 1985 году президент Али Насер Мухаммед отправил своего охранника в зал заседаний кабинета министров для того, чтобы расстрелять из автомата весь состав Политбюро. Центр очень боялся, что Саудовская Аравия, возможно, захочет использовать свое огромное богатство для организации переворота и свержения марксистского режима в Южном Йемене. И все же главная угроза существованию Южного Йемена исходила не извне, а от собственных кровожадных и некомпетентных правителей.
