Принципиально новые возможности для расширения советского влияния в третьем мире открылись в 70-х годах в Африке. Крах португальской империи и свержение императора Хайле Селассие привели к появлению в трех крупных африканских государствах — Анголе, Мозамбике и Эфиопии — самозваных марксистско-ленинских режимов. В Анголе, богатейшей португальской колонии, конец португальского правления в 1975 году был отмечен полномасштабной гражданской войной между марксистским Народным движением за освобождение Анголы (МПЛА), с одной стороны, и Национальным фронтом освобождения Анголы (ФНЛА) вместе с Национальным союзом за полную независимость Анголы (УНИТА) — с другой.
После переговоров между лидером МПЛА Агостиньо Нето и резидентурой КГБ, прошедших в Лусаке в августе 1971 года, через Браззавиль начались крупномасштабные поставки советского оружия ангольскому режиму. Однако решающим фактором в борьбе за власть стало направление в Анголу летом 1975 года кубинских войск. В феврале 1976 года режим МПЛА получил официальное признание Организации африканского единства (ОАЕ), как законное правительство Анголы. Хотя кубинская интервенция приветствовалась Москвой, которая обеспечивала ее и оружием и транспортными самолетами, инициатива исходила из Гаваны. Кастро смотрел на Анголу, как на возможность провозглашения себя великим революционным вождем мирового масштаба и как на удачный случай укрепления былого революционного духа на самой Кубе. Хотя ЦРУ и направляло УНИТА потихоньку деньги, после Вьетнама Вашингтон уже не решался серьезно противостоять кубинскому присутствию в Анголе.
Офицеров разведслужбы МПЛА направляло на годичные учебные курсы в андроповский институт ЛГУ. Там некоторые из них вербовались КГБ. Сам Нето, который несколько раз приезжал в Москву для лечения, получил от Центра оценку «психанутый». Центр считал, что Нето не способен справиться с фракционной борьбой в МПЛА. Однако никакого надежного и способного преемника у него в МПЛА не было. Резидентуры КГБ в странах черной Африки получили указание наблюдать за внутренней борьбой в МПЛА и своевременно выявить угрозу Нето. Первоначальный идеализм, порожденный борьбой за независимость Анголы, скоро захлебнулся во фракционной борьбе, бесхозяйственности и общественном недовольстве. В 1977 году Нето подавил возникший было мятеж. В 1978 году он снял с должности премьер-министра и трех его заместителей. Чтобы помочь ему держать оппортунистов в руках, советники из восточногерманской службы государственной безопасности (ССД) создали ангольскую службу безопасности — Управление информации и безопасности Анголы (ДИЗА), находящуюся под личным управлением президента. В 1979 году недавно созданный 20 отдел ПГУ отправил в советское посольство своего офицера по связи. По просьбе ангольской стороны советником в ДИЗА был направлен Вадим Иванович Черный, бывший сослуживец Гордиевского по Копенгагену. Выбор этот был весьма сомнительным, поскольку Черный любил выпить и не имел никакого опыта в области мер безопасности. Вскоре его работа в Анголе была прервана — во время очередного запоя Черный упал и сломал руку. Однако по возвращении он сообщил Гордиевскому, что, несмотря на досадное недоразумение, МПЛА наградило его медалью. После множества подобных примеров Гордиевский пришел к выводу, что только таких офицеров, как Черный, КГБ и посылал в качестве советников к тем «прогрессивным» режимам, доверие к которым в Москве упало.
После того, как Нето умер в Москве от рака в 1979 году, ситуация в Анголе еще больше ухудшилась. При поддержке ЮАР УНИТА окончательно закрепилась в стране. Сообщения КГБ из Лусаки в начале 80-х годов характеризовали руководство МПЛА, как раздробленное, а экономическое положение, как катастрофическое. Оценки Международного отдела ЦК КПСС не были оптимистичнее. Один из старших советников ЦК Николай Шишлин в частной беседе предсказывал, что растущие проблемы в МПЛА вскоре могут привести ее к соглашению с ЮАР.
Советская политика в отношении бывшей португальской колонии в Восточной Африке — Мозамбике — мало чем отличалась от Анголы. Хотя и без кубинского вмешательства, Москва направляла оружие марксистскому Фронту освобождения Мозамбика (ФРЕЛИМО), возглавляемому президентом Саморой Машелом. Машел пришел к власти летом 1975 года. Как и МПЛА, ФРЕЛИМО направлял ежегодный контингент своих разведывательных кадров в Москву для подготовки в андроповском институте. Точно как и в Анголе, советники из восточногерманской ССД помогли Мозамбику образовать собственную Национальную службу народной безопасности (СНАСП), которая отправляла диссидентов в трудовые лагеря, официально значившиеся «центрами умственной деколонизации». Двадцатый отдел ПГУ имел своего сотрудника и в советском посольстве в Мапуту (как и в Луанде). Поначалу Центр возлагал на Машела больше надежд, чем на Нето. Во время борьбы за независимость Машел проявил себя как искусный партизанский вождь и обаятельный политический лидер.
Однако к началу восьмидесятых годов данные КГБ из дипломатических источников из Мозамбика были еще пессимистичнее, чем из Анголы. В 1981 году Машел начал «кампанию законности», направленную на обуздание коррупции и легализацию пыток СНАСП. Годом позже он объявил об увольнении 466 офицеров СНАСП. Однако на Московский центр это впечатления не произвело. Отчет из посольства Мапуту за 1984 год, который был разослан другим советским посольствам и резидентурам КГБ, представлял собой самое язвительное описание дружественного режима третьего мира на памяти Гордиевского. В нем руководство ФРЕЛИМО характеризовалось как разобщенное, некомпетентное и коррумпированное. Отмечалось среди прочего и то, что экономика Мозамбика лежала в руинах. Органы местного управления и юридические власти были также разобщены. Сообщалось, что ФРЕЛИМО лишь на словах был привержен социализму. При поддержке Южной Африки набирало силу Мозамбикское национальное сопротивление (МНС). Несмотря на свой пессимизм, Центр все же был удивлен подписанием договора о ненападении между ФРЕЛИМО и Южной Африкой в марте 1984 года. В Москве опасались, что Советскому Союзу будет не по средствам удержать Мозамбик от сближения с Западом.