В те годы, когда Наджва продолжала рожать детей, а Омар достиг возраста, в котором начал осознавать, что его жизнь отличается от жизни других детей, Усама бен Ладен всецело посвящал себя конфликту в Афганистане. Война велась с переменным успехом: русские занимали главные города страны, а моджахеды (в число которых входил и Усама) вели партизанскую борьбу. В 1980–1985 годах советские войска предприняли девять крупных наступательных операций, приведших к ожесточенным боям.

В 1985 году Абдулла Аззам и Усама организовали официальную контору, назвав ее «Служебным отделом»: туда посылали на обучение мусульман-волонтеров, которых затем отправляли в Афганистан. Усама больше не желал ограничивать свою деятельность организацией поставок оружия и провианта. Он хотел расширить участие в джихаде, помогая организовать учебные лагеря для тренировки бойцов, строя дороги и создавая собственный отряд бойцов из арабских стран. К тому времени он начал участвовать в сражениях и рисковал жизнью бок о бок со своими людьми, получая серьезные ранения.

Усама также познакомился с главными джихадистами Египта, вдохновившими его на дальнейшую деятельность. Все они придерживались одинаковых взглядов, мечтая возродить исламский мир сразу после того, как Советы потерпят поражение. Эти люди позже стали самыми ярыми последователями Усамы, включая Мухаммеда Атефа, доктора Аймана аль-Завахири, Абу Убайдаха аль-Баншири, Абдуллу Ахмеда Абдуллу и Омара Абделя Рахмана, слепого шейха из Египта.

Поскольку Усама бывал в Пакистане и Афганистане чаще, чем в Саудовской Аравии, он нашел для своей семьи дом в Пешаваре, чтобы его жены и дети проводили там лето. Усама близко познакомил своего старшего сына, Абдуллу, с ситуацией в Афганистане — он брал его с собой в лагерь повстанцев в Джаджи, где жизнь мальчика была в нешуточной опасности. Неожиданно для себя Усама подвергся серьезной критике многих членов семьи и других лидеров джихада за этот поступок, но это был лишь первый из длинной цепочки случаев, когда он принуждал лишенных его энтузиазма сыновей выступать в первых рядах бойцов джихада, ставшего его ярой страстью.

В апреле 1988 года, через девять лет и пять месяцев после первого вторжения советских войск в Афганистан, представители Афганистана, Советского Союза, Соединенных Штатов и Пакистана встретились для подписания соглашения, по которому СССР обязался вывести свои войска с территории Афганистана. Афганистан и Пакистан согласились не вмешиваться в политические и военные дела друг друга. А США обязались прекратить поддержку антисоветских группировок в Афганистане.

Наставник Усамы, Абдулла Аззам, воспользовался случаем для расширения своей организации и базы, которую верующие могли использовать в целях борьбы за создание совершенного исламского мира. Полностью согласный с ним Усама созвал организационное совещание, которое получило название «Аль-Каида аль-Аскарийя», что переводится как «Военная база», а позже название укоротилось и превратилось просто в «Аль-Каиду», что означает «база» или «фундамент». Первое совещание состоялось в доме семьи бен Ладена в Пешаваре в августе 1988 года.

Основатели новой организации заявили, что «Аль-Каида» станет проводить глобальную кампанию, используя как духовное оружие исламской веры, так и военное, то есть будет поддерживать ислам как ненасильственными, так и насильственными мерами. Цели организации: избавление мусульманского мира от пагубного западного влияния, свержение монархов и светских правителей и установление ислама как единственной религии во всем мире. Поскольку война в Афганистане подходила к концу, у Усамы появилось больше времени, которое он мог посвящать грандиозным планам «Аль-Каиды».

После того как Усама взял на себя роль лидера этого движения, между некоторыми его последователями возникли трения. Самые серьезные разногласия были между Абдуллой Аззамом и доктором Айманом аль-Завахири, оба они боролись друг с другом за поддержку Усамы, в том числе финансовую. И если Абдулла Аззам не одобрял насилия, направленного против братьев-мусульман, Завахири был лишен подобной щепетильности. Со временем трения между ними разрослись, превратившись в большую проблему для движения.

15 февраля 1989 года Усама и его бойцы заявили о великой победе. К несчастью, после ухода русских афганские полевые командиры начали ссориться между собой, и каждая группировка была полна решимости захватить власть в изнуренной войной стране. Усама приложил ряд усилий для сплочения лидеров страны, но все его попытки не увенчались успехом.

После завершения войны, когда «Аль-Каида» искала возможность расширить свое движение до глобальных масштабов, на жизнь Абдуллы Аззама было совершено несколько покушений. 24 ноября 1989 года Аззам и двое его сыновей были убиты взрывом трех противопехотных мин, сработавших, когда они ехали в автомобиле в мечеть Пешавара на молитву. Много версий высказывалось в отношении виновников его смерти, но большинство полагало, что за убийством стоял Завахири.

Погибший в возрасте сорока девяти лет, Абдулла Аззам был, вероятно, единственным человеком, который мог бы предостеречь Усаму от совершения в будущем нападений на правителей Саудовской Аравии и Америку.

Вскоре Усама вернулся в Саудовскую Аравию, в Джидду, человеком, в котором пробудилось совершенно новое политическое, религиозное и военное сознание. Он продолжал расширять «Аль-Каиду» и стал активно встречаться с другими арабами, разделявшими его взгляды.