离开沙特之后，本·拉登最初的想法是回到阿富汗，回到这个他曾经生活和战斗过的地方，然而等到他真正到了那里之后，才发现情况和他预想的完全不一样。苏军撤走之后，原本团结一致进行抗战的各支武装力量，居然立即开始相互残杀。这就导致阿富汗人民不但没有过上幸福的生活，反而生活得更加水深火热。
当时本·拉登的想法还比较天真，因为对这些武装力量普遍都有过帮助，而且本·拉登的军事势力在阿富汗也有遗留，他认为自己可以充当和事佬，即说服各派武装力量的首脑坐下来进行和谈，在阿富汗建立起一个共同管理下的联邦国家。在会议发起之后，各支武装力量也确实都参加了，并在会议上做出了同意本·拉登建议的打算。但是本·拉登在阿富汗的情报系统很快向他报告，很多首领对他的意见都却是阳奉阴违，其中一些激进分子甚至想要暗杀他。
面对这样的传言，本·拉登通过分析认为，这些极端分子只是少数，他的提议最终一定可以得到通过。然而在出席一次活动时，本·拉登居然真的遭到遭遇杀手的刺杀，还好他的情报和保卫人员及时发现并加以制止，而对于本·拉登的这次遇袭事件，几乎所有武装派别的头目都保持了沉默。
换句话说，希望本·拉登离开阿富汗，是所有人集体的心声。此时，和本·拉登关系最为密切的塔利班组织也向本·拉登透露，这些头目很多都得到了国际势力的支持，其中包括苏联和美国，即使这些头目愿意和谈，在背后势力没有同意的情况下，也是不可能的，针对本·拉登的暗杀行动也才刚刚开始。因为情况已经坏的得不能再坏，本·拉登最终决定离开阿富汗，碰巧的是就在这个时候，苏丹当局对他发出了邀请。
早在1989年，巴希尔就在图拉比的支持下取得了苏丹政权。此时，由于美军进入海湾地区，巴希尔和图拉比认为神圣的伊斯兰世界领土被玷污，旋即组织召开了泛阿拉伯和伊斯兰大会（PAIC），并立即吸引了几乎全世界的伊斯兰武装力量参加。本·拉登看到苏丹的伊斯兰运动如此火热，又接到了热情的邀请，自然非常欣喜地来到了苏丹。而本·拉登因为名声在外，在到达苏丹后，也很快被接到了首都喀土穆，并得到了图拉比的亲切接见。
由于同属坚定的伊斯兰教信徒，本·拉登和图拉的观点非常接近，二人在交换了彼此想法之后，都认为自己又多了一个真挚的朋友和坚定的战友。在受到西方和本国王室的排挤之后，本·拉登也终于找到了一个可以安身立命的地方，而图拉比对于本·拉登的影响，也让他对沙特王室彻底绝望，从而走上了绝对强硬的武装对抗西方世界之路。
随后，图拉比亲自在喀土穆为本·拉登安排了居所，为了表示神圣的穆斯林兄弟情谊，图拉比还将本·拉登的住址安排在了自己家附近，并派出了自己的亲卫部队负责其人身安全。1992年，在苏丹各地进行参观之后，本·拉登终于看到了自己梦寐以求的革命景象，因为对伊斯兰圣战感到有了前所未有的希望，本·拉登最终决定在喀土穆定居下来。与此同时，本·拉登对于图拉比和巴希尔政权的支持也是非常慷慨的，后来据美国中央情报局公布的数据显示，再缴纳了数额不菲的会员费用之后，本·拉登成为巴希尔政权的组成者之一，而本·拉登在此之后，又累计向巴希尔政权提供直接资金支持达到五千万美元，另外还包括很多重要的军事设施建设，以及民众所需的基础设施建设等间接投资。
在苏丹站稳脚跟之后，本·拉登除了进行必要的宗教活动之外，也开始考虑自己的投资回报问题，至此，他的商人天赋也得到了充分发挥。因为成了苏丹政府的负责人之一，又具有丰富的国际人脉资源，还掌握着大量世界先进的科学技术和设备，本·拉登很快在苏丹建设了自己的贸易网络，领域不仅涉及他熟悉的金融和能源方面，还在交通、农业、进出口贸易和医药等方面有所建树。这些都为本·拉登赚取了巨额财富，远远超过他对苏丹政府投入的五千万美金。不过正如本·拉登自己所说：“我的事业需要钱财，但我本人并不需要。”本·拉登虽然在苏丹聚集了富可敌国的财富，但他全部都用来建设自己的组织，继而完成他的理想。于是，本·拉登利用国际贸易的便利，将散落在世界各地的穆斯林圣战者运送到苏丹，进行培训之后在派往世界各地潜伏。后来本·拉登的财政负责官员曾经做出统计，因为要避开美国等西方势力的视线，本·拉登仅仅将这些圣战者运送到苏丹，就需要支付高达数百万美元的高昂费用。
与此同时，因为生活环境相对稳定，本·拉登还得以将自己的妻儿接到喀土穆居住。据本·拉登的妻子后来回忆，本·拉登在此期间继续着苦修士般的私人生活，他尤其喜欢在工作之余种植玉米和向日葵，本·拉登在收获时的喜悦，简直超过他在政治和商业上取得任何成就的喜悦。此外，本·拉登还要求妻女尽量学会并遵从他的私人生活方式，以保证对真主阿拉的虔诚信仰。比如在空闲时间里，本·拉登会教他的儿女们辨认各种农作物和蔬菜，并且告诉他们各种注意事项，俨然是一个精通种植的老农。一年夏天，由于喀土穆的气温过于炎热，本·拉登对于现代化电器又比较排斥，他还曾带着自己的孩子去选购建材，并和他们一起建造了几间树屋。如果是一般人，建造这样的树屋也许会像游戏一样随便，但是本·拉登却非常认真，看着一座座规整的小木屋在树干上排列，即使是专业的木匠也会发出赞叹。后来曾经有媒体介绍说，本·拉登年轻的时候曾经学过木匠，这一点也许在此可以得到认证，而且作为一个传统的建筑商家族子弟，又曾长期从事建筑生意，本·拉登对于木匠多少会有所了解。
事业方面，本·拉登在苏丹的组织建设是卓见成效的，截止到1994年底，他已经成功训练并武装了五千名坚定的圣战者，随时准备听从他的号令扑向世界各地的目标。与此同时，本·拉登还从世界各地搜罗退伍军人，然后挑选其中最精悍的人充当教官，在喀土穆郊区建立了二十三个训练营，并由此开始源源不断地为本·拉登的基地组织输送“新鲜血液”。然而，因为苏丹的周边都是比较温和的穆斯林国家，其国内的极端分子全都跑到了苏丹境内避祸，并在发展壮大后继续回到国内制造事端。本·拉登作为坚定的伊斯兰信徒，又心怀沙特人民，自然也不会敢于寂寞，只不过他的城府较深，思考问题的目光也比较长远，所以他的全部精力都用在编制自己的组织网络，并且逐渐扩散在全球各个国家。到1995年前后，苏丹巴希尔和图拉比政体的影响力上升到巅峰时刻，巴希尔不仅一再深化本国的极端伊斯兰政权，还公开表示支持世界范围内的泛伊斯兰运动，也就是支持伊斯兰极端势力推翻本国政府。
这样一来，还没等美国等西方势力还没有找上门，苏丹周边的一些国家已经怨声载道。首先是艾尔及利亚议长遭到袭击，然后是突尼斯总统险些遇刺，卡扎菲险些遇刺，埃及总统穆巴拉克也遇到杀手行刺事件等。而这些国家的情报和调查人员所提供的证据都显示，这些事件都不同程度和巴希尔及图拉比有关。1993年2月26日，伊斯兰极端分子的怒火终于燃烧到美国本土，一辆装满炸药的货车驶入纽约世贸中心大楼地下停车场，后被恐怖分子用遥控装置引爆，造成多人死伤和大量经济损失。而最终的调出结果也显示，被确定的六名涉案人员全部为苏丹人，其中包括两名大使馆人员，另有数名苏丹外交人员涉嫌牵连此案，遭到美国政府驱逐。如此一来，不仅美国开始关注并积极介入苏丹造成的南非紧张局势，联合国也不得不对苏丹实施经济制裁，要求其放弃对他国“极端分子”的庇护，坚决杜绝伊斯兰极端活动。
因为国际压力过重，巴希尔和图拉比政体最终只能选择屈服，巴希尔于同年12月宣布收回支持泛伊斯兰运动的承诺。图拉比也开始知会聚集在苏丹的各国伊斯兰极端势力，授意他们尽快开始有组织的进行撤离，继续残留的小股势力也转入地下活动，但仍有不少遭到美国情报人员的俘获。1996年，作为苏丹最具势力的私人武装组织头目，同时又在世界范围内建立了强大的情报网络，本·拉登最后一个成建制地带着基地组织离开苏丹。不过此时此刻，本·拉登的基地组织经过四年长足发展，已经完全有能力担起泛伊斯兰运动中心的任务。至于本·拉登，他不仅是这样想的，同时也是这样做的。
