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