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