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