Хасан аль-Тураби, духовный лидер Судана и выдающаяся фигура воинственного суннизма, всегда стремился к распространению исламизма в Африке. Несмотря на драматический исход исламистского джихада в Сомали — вызвавший вывод войск США, — Хартум и Тегеран полностью осознавали, что они не достигли никаких значимых целей. После победы исламистов в Могадишо так и не было установлено исламистское правительство, а началась братоубийственная война между различными вооруженными группировками. Об этом постоянно напоминала разгорающаяся на юге Судана гражданская война. Кроме того, иностранная помощь, поступавшая в южный Судан через страны Восточной Африки, была дополнительным стимулом нанести удар как по этим странам, так и по их стратегическому защитнику — Соединенным Штатам.
Усиление исламистского подполья в Восточной Африке началось сразу же после вывода американских войск из Сомали, в начале 1994 года. Айман аль-Завахири, бывший в то время старшим командиром в Сомали, считал наращивание сил в Кении настолько важным, что занялся этим лично, совершая многочисленные тайные поездки в Найроби и Момбасу. Костяк нового вооруженного отряда в Кении составляли иорданские «афганцы». Первоочередной их задачей было закрепиться в Кении и подготовиться к приему других исламистов, которые должны были прибывать из Пакистана.
Одновременно исламистские сети в Восточной Африке занялись вопросами снабжения — переправкой наркотиков, выращиваемых и производимых в Афганистане и Пакистане, и отмыванием денег для финансирования быстро расширявшихся исламистских сетей в Западной Европе и Соединенных Штатах. Основными портами, которыми пользовались — и до сих пор пользуются — исламисты, были Занзибар (Танзания) и Момбаса (Кения): отсюда наркотики переправлялись в Западную и Восточную Африку и далее на Запад. Растущее значение Восточной Африки для системы материального обеспечения террористов во всем мире делало этот регион еще более привлекательным местом для проведения зрелищных террористических актов.
Хартум попытался задействовать двух видных исламистов, которые находились в Найроби с 1994 года как резервные командиры, но они оказались не готовы к решительным действиям. Первым из них был Мустафа Махмуд Сайд Ахмад, египетский «афганец», родившийся в Заире и закончивший университет аль-Азхар. Действуя из своей базы в Кувейте, он выполнял шпионские задания для исламистов Кувейта и Египта. Но к середине 1990-х годов он уже отвернулся от воинственного исламизма. Другой командир был Вадих эль Хейдж, американец арабского происхождения, который служил секретарем бин Ладена в Хартуме с середины 1980-х годов. Хотя он и был искренне предан делу исламизма, он оказался неподходящим человеком, потому что привлек к себе внимание. В августе 1997 года отряды кенийской службы безопасности и ФБР устроили облаву в доме эль Хейджа, в результате чего он как оперативный сотрудник «погорел». Оба командира в 1997 году были высланы из Найроби, а их место заняли новые, более уверенные в себе.
Наиболее важное изучение ситуации в Восточной Африке было проведено в сентябре 1996 года под прикрытием визита иранского президента Али Акбара Хашеми-Рафсанджани в шесть стран Восточной Африки — ЮАР, Зимбабве, Танзанию, Судан, Уганду и Кению. Группа старших офицеров разведки, сопровождавших Хашеми-Рафсанджани, воспользовалась этим случаем, чтобы лично изучить ситуацию в регионе. В середине октября Хашеми-Рафсанджани пояснил, что его визит «предоставил исламскому Ирану историческую возможность помочь в развитии и восстановлении африканского континента». Он отметил «тщетные попытки США оказывать давление на африканские страны, чтобы помешать им укрепить отношения с Ираном» и заключил, что «страны и народы Африки оценили выгоды торговых и экономических связей с исламским Ираном и уже освободились от уз эгоистичной политики Запада».
В середине ноября 1996 года Джавид Горбан Огли, генеральный директор африканского отдела в иранском Министерстве иностранных дел, подтвердил первостепенную важность Восточной Африки для Тегерана: «Сегодня Африка стала важным, узловым пунктом в мире. Даже американцы признают, что африканские народы полностью осознают суть исламской революции и симпатизируют нашей стране и нашей революции. Это привело к укреплению наших связей с африканскими государствами, что, конечно, не соответствует объявленной Вашингтоном политике изоляции Ирана». То, что на эту должность был назначен именно Огли, очень важно, поскольку он является бывшим послом Ирана в Алжире, где поддерживал деятельность исламистов, включая террористическую и подрывную.
Зимой 1996–1997 года значение Восточной Африки для стратегических планов Ирана коренным образом изменилось. Иранцы всерьез занялись модернизацией своих военно-морских сил. Получение авианосцев от Китайской Народной Республики и поступление из России третьей подводной лодки КИЛО (одна из наиболее современных, бесшумных и смертоносных неядерных подводных лодок в арсенале российской армии) укрепило уверенность Тегерана в способности проводить боевые операции в более широкой области. Эти поставки оружия были только первой стадией крупной и серьезной программы расширения морского флота, основанной преимущественно на приобретении у Китая многочисленных боевых кораблей и рассчитанной на несколько лет. Когда эта программа завершится, у Ирана будет самый мощный флот в зоне Персидского залива.
В начале 1997 года Иран получил доступ к военно-морским базам в Мозамбике. В обмен на многостороннюю военную помощь, иранскому флоту было дозволено использовать портовые сооружения в Мапуту и Накале — они были построены советскими и кубинскими специалистами в годы холодной войны. В соглашении между Ираном и Мозамбиком особо оговаривалось право иранцев использовать эти портовые сооружения для своих подводных лодок.
Истинное значение этих событий становится очевидным в контексте дерзкой военной доктрины Тегерана: предупредить — или даже самим нанести — превентивные удары по войскам США в случае серьезной эскалации конфликта в Персидском заливе. Военные планы Тегерана в Персидском заливе зависят от предотвращения быстрой военной интервенции США, и потому для Тегерана чрезвычайно важно не допустить своевременного прибытия американских военно-морских сил. Тегеран полон решимости нарастить военный потенциал, чтобы осуществить эту миссию. Учитывая неравенство сил американского и иранского флота, единственный путь для иранцев предотвратить американскую интервенцию — это навязать бой флоту США вдали от Персидского залива.
Тегеран продолжил поднимать ставки в противостоянии Соединенным Штатам и арабским странам Персидского залива, особенно Саудовской Аравии. В ожидании нового раунда балансирования на грани войны и возможной вспышки военных действий на Ближнем Востоке, Тегеран предупредил арабские государства, чтобы они не позволили США начать действия против Ирана. В начале февраля 1997 года аятолла Хаменеи открыто высказал свои угрозы во время своей проповеди в День аль-Кудс. (День аль-Кудс — иранский праздник, приходящийся на последнюю пятницу месяца рамадана, когда мусульмане клянутся освободить святые места, оккупированные неверными.) «Если кто-нибудь из этих иностранцев в Персидском заливе сделает опрометчивый шаг, то в первую очередь пострадает та страна, которая пригласила сюда этих иностранцев», — заявил он.
Тем временем официальный Тегеран начал широкую кампанию по укреплению исламистского присутствия в Африке, уделяя первостепенное внимание тем шести государствам, которые посетил Хашеми-Рафсанджани. В начале весны 1997 года эта кампания была в полном разгаре. План кампании был разработан сотрудниками разведки, сопровождавшими Хашеми-Рафсанджани в его поездках. Он был представлен духовному вождю Ирана аятолле Хаменеи, который призвал к гораздо более решительным и далеко идущим действиям. Пересмотренный план был оформлен Али Хиязи, руководителем личного офиса Хаменеи. В начале 1997 года, после тщательного изучения и незначительных изменений, внесенных специалистами разведки, план был представлен Верховному совету национальной безопасности, возглавляемому Хашеми-Рафсан-джани, для одобрения и санкционирования его осуществления.
Совет единодушно одобрил план. Он также выделил 9 миллионов долларов специально на разведывательные операции в Восточной Африке. ИРГК получил дополнительные средства для подготовки специальных вспомогательных отрядов. Кроме того, под ширмой «Управления исламской культуры и воспитания» в Тегеране была создана штаб-квартира для наблюдения и координации деятельности террористов.
В начале 1997 года на дипломатические и псевдодипломатические должности в иранских представительствах в Восточной Африке были назначены опытные сотрудники разведки. Эти назначения точно отражали приоритеты Тегерана.