Уже в 1961 году кубинское судно доставило оружие алжирским патриотам, борющимся за свою независимость от Франции, а на обратном пути привезло детей и раненых. Куба оказывала помощь молодой Алжирской народно-демократической республике, направляя туда медицинский персонал и военных советников. Осенью 1963 года Алжир подвергся агрессии со стороны Марокко, власти которого при поддержке США попытались захватить алжирские месторождения. Куба направила в Алжир танковый батальон, несколько артиллерийских расчетов и около тысячи солдат. Командовал ими Эфихенио Амейхейрас, ветеран «Гранмы» и Сьерра-Маэстры. Появление танков охладило пыл марокканцев, они были вынуждены отступить, а кубинцы одержали первую победу за пределами собственного государства. Миссия в Алжире породила кубинскую традицию широкомасштабных программ оказания медицинской помощи развивающимся странам.
В июле 1964 года в центральных и восточных районах Конго вспыхнуло мощное восстание, вызванное назначением Чомбе, сторонника правого прозападного курса, временным премьер-министром страны. Повстанцы, называвшие себя «Simba» (на суахили «лев»), были преимущественно молодыми людьми, отстаивающими коммунистические лозунги. При этом они верили в магические ритуалы, воевали копьями и обмазывались соком трав, считая, что это защитит их от пуль. Номинально повстанцев возглавил бывший министр образования в правительстве Лумумбы Пьер Мулеле. При поддержке СССР и Китая, а также соседней Танзании повстанцы расширили свои территории и продвинулись на север. 4 августа 1964 года был взят Стэнливиль и 5 сентября провозглашена Народная Республика Конго.
Американцы были в панике – им виделся второй Вьетнам. На заседании СНБ США 6 августа 1964 года говорилось: «Стэнливиль находится в руках повстанцев. Всё восточное Конго может последовать за ним в течение ближайших дней; Катанга, Леопольдвиль и всё центральное правительство могут рухнуть в течение ближайших недель». Председатель объединенного комитета начальников штабов генерал Эрл Уилер отдал приказ разработать план широкомасштабного военного вмешательства. В Конго направили четыре транспортных самолета С-130, три вертолета и 50 бойцов спецназа. ЦРУ начало операции по бомбардировке повстанцев с воздуха, взяв на содержание ВВС Конго и наняв 79 пилотов, в основном из числа кубинских эмигрантов-контрреволюционеров. Для наземных операций был завербован известный британский солдат удачи Майкл Хоар («Бешеный Майк»), который сформировал отряд «Коммандо 5» из белых наемников, среди которых были и бывшие нацисты. Этот отряд получил известность из-за своих зверств в зоне конфликта – убийств мирных жителей, пыток, грабежей и изнасилований. В интервью прессе сам Хоар описал своих людей как «диких головорезов». Финансирование Хоара полностью осуществляло ЦРУ, в том числе резидент ЦРУ в Конго Бенджамин Хилтон Кушинг.
1 ноября 1964 года наемники Хоара и части Чомбе начали наступление на Стэнливиль. В ответ на это повстанцы взяли под стражу оставшееся белое население Стэнливиля, рассчитывая использовать его в качестве козыря в переговорах с Чомбе. Для освобождения заложников в Конго прибыли бельгийские парашютисты при поддержке американской авиации. 24 ноября в рамках операции «Красный дракон» бельгийцы высадились в Стэнливиле и приступили к освобождению заложников. Через два часа после высадки бельгийцев в город вошла колонна Хоара. Началось повальное мародерство, причем наемники активно грабили дома «спасенных» ими белых. Армия Чомбе грабила и убивала черных. В Вашингтоне с удовлетворением отмечали роль ЦРУ во взятии Стэнливиля: «Самолёты ЦРУ наводили ужас на симба, которые осознали, что их магия не спасет от пулеметов 50-го калибра и авиационных пушек».
Казалось, что восстание симба было подавлено. Но с этим не был согласен как минимум один человек – команданте Че Гевара. Для себя он уже решил, что в Конго американцы получат второй Вьетнам. Как указывает Александр Владимирович Корольков в статье «Становление кубинского интернационализма (1959–1975)», пребывание Че Гевары в Конго часто представляется как частная авантюра. На самом деле его действия осуществлялись в рамках хорошо продуманных стратегических решений, которые позднее подтвердили свою правоту.
В конце 1964 года Че вылетел в Африку и 2 января 1965 года встретился с президентом Конго-Браззавиль Альфонсом Массамба-Деба, придерживавшимся левых взглядов. Массамба-Деба поддерживал повстанцев соседнего Конго и стремился объединить эти две страны. Тогда, учитывая границу со вставшей на путь социалистического развития Танзанией, новое большое социалистическое Конго смогло бы контролировать всю центральную часть африканского континента. К тому же Массамба-Деба поддерживал Народное движение за освобождение Анголы (МПЛА). Ангола, граничившая с Конго, с 1961 года воевала против португальских колонизаторов. 5 января Че встретился с лидером МПЛА Агостиньо Нето, пообещав движению военную помощь Кубы. Именно с этой беседы началось участие кубинцев в ангольских событиях, завершившееся спустя 30 лет победой Кубы в борьбе против США и ЮАР.