Оперативный план, разработанный созданным Военным комитетом, включал организацию взрывов в двух отелях в центре йеменской столицы, где транзитом на пути в Сомали останавливались американцы, и обстрел из ручных противотанковых гранатометов (РПГ-7) транспортных самолетов ВВС США, находящихся в аэропорту йеменской столицы.
Поскольку уровень подготовки, боевиков «Джихад аль-Ислами аль-Ямани» оставлял желать лучшего, бин-Ладен усилил диверсионные группы «арабскими афганцами» — специалистами взрывного дела. Все финансовые расходы взяла на себя «Эль-Каэда», деньги переводились через банковские счета йеменских компаний, принадлежавших бин-Ладену.
Необходимое вооружение и боеприпасы были доставлены из соседнего Судана через Красное море на небольших рыбацких шхунах, разгрузка снаряжения проводилась на отдаленном участке побережья Йемена, в районе аль-Кауваха. Руководил подготовкой боевиков специально вызванный из Афганистана инструктор ливийского происхождения, бин-Ладен дорожил этим человеком, за день до теракта он покинул Йемен и вернулся в Афганистан.
29 декабря 1992 года в центре Адена, между отелями «Голден Мур Отель» и «Аден Отель» прозвучал мощный взрыв. Несмотря на сильные разрушения, человеческие жертвы были небольшими. Погибло 2 человека, в том числе австралийский турист, 20 случайных прохожих были ранены. Никто из американских военнослужащих не пострадал, накануне теракта они были отправлены в Сомали. Ни одна террористическая организация не взяла на себя ответственность за взрыв.
Силы йеменской полиции и службы безопасности были приведены в состояние боевой готовности. Очевидно, что целью теракта было нападение на американцев. Благодаря предпринятым мерам безопасности, удалось предотвратить еще один теракт в столичном аэропорту. Возле ограждения взлетно-посадочной полосы была захвачена группа боевиков, вооруженная автоматами Калашникова и ручными гранатометами.
Они готовились обстрелять транспортные самолеты ВВС США, подготовленные к отправке в Сомали. Эффективные оперативно-розыскные действия позволили по горячим следам раскрыть преступление, 8 января 1993 года, спустя 10 дней после теракта, был арестован шейх Тарика аль-Фадли и большинство его людей, преступные связи исполнителей прямо указывали на бин-Ладена.
Бин-Ладен со свойственными ему хладнокровием и рассудительностью сделал необходимые выводы. Операция, по его мнению, потерпела полный провал из-за низкого профессионализма людей, ответственных за сбор разведывательной информации и планирование операции. Йеменская группа не только не выполнила задание, но и поставила под угрозу провала всю региональную сеть «Эль-Каэды». Больше «Эль-Каэда» и ее руководитель не допустят столь грубых промахов. Взрыв в центре йеменской столицы был только началом целой череды разрушительных терактов с многочисленными невинными жертвами — христианами, мусульманами, иудеями, индусами…
К тому времени лидирующую позицию в организации вслед за бин-Ладеном прочно занял Айман аль-Завахири, объединивший с «Эль-Каэдой» свою собственную террористическую фракцию. Союз бин-Ладена и аль-Завахири, их энергия, опыт и финансовые возможности оказались весьма продуктивными, теперь «Эль-Каэда» могла контролировать многие организации исламских радикалов типа «Джихад аль-Ислами» и действовать по всему миру. Во многом этому способствовала поддержка духовных авторитетов, в первую очередь слепого шейха Умара Абд аль-Рахмана — лидера египетских исламистов. Это время можно назвать временем окончательного завершения строительства организации и оформления ее идеологии — радикального воинствующего исламизма — Всемирного Исламского Фронта Джихада против крестоносцев и евреев. Роль Аймана аль-Завахири в этом процессе, его «архитектора» и идеолога, не уступает роли самого бин-Ладена.