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