本·拉丹乘坐一架租来的飞机从喀土穆来到贾拉拉巴德，途中在阿联酋加油并作短暂停留。随行的还有他的家人和保镖，以及那些自1988年他的组织在阿富汗建立以来一直在他身边的“基地”组织成员。另外的几十个“斗士”搭乘晚一些的航班到达。
虽然本·拉丹的目的地是阿富汗，巴基斯坦却是他能够利用阿富汗作为重整旗鼓、发动反美战争的基地的一个关键要素。
在作为一个国家存在的最初25年，巴基斯坦的本体来自于伊斯兰教，但它的政治却由世俗决定。军队曾经是，后来也一直是该国最强大和最受人尊重的机构，但军队长期并且继续为与印度的敌对关系所困扰，特别是在克什米尔的领土争端问题上。
自20世纪70年代起，宗教逐渐成为巴基斯坦政治中的强大力量。在1977年的一次政变后，军事领导人转向伊斯兰小组寻求支持，而原教旨主义者的地位也日渐突出。南亚国家本来就采用了伊斯兰原教旨主义的固有形式，这种形式是从19世纪岱欧邦的一个印度村庄学校发展而来的。在受沙特阿拉伯资助的一些机构的培育下，伊斯兰瓦哈比学校的影响也有所增强。并且，发生在阿富汗的战争使得巴基斯坦变成了大量的阿富汗难民的家园，但是他们一般不受欢迎。而糟糕的巴基斯坦教育系统根本无法接纳这么多的难民，于是政府就大量起用私人投资的宗教学校作为免费的替代物。这些学校培养出来的大量年轻人虽然掌握了不少伊斯兰教方面的知识，却并不具备适应市场需要的技能。
巴基斯坦的统治者发现，大量的阿富汗热血青年对其本国来说是潜在的危险因素，但在国外却很有用场。那些参加塔利班运动、宣扬伊斯兰法律的残忍一面的人，有可能会给混乱的阿富汗带来秩序，并使其成为合作同盟。这样，他们可能会在边界问题上给巴基斯坦带来更大的安全感，对这些问题的解决，巴基斯坦军事官员一直希望实现他们所谓的“战略深度”。
如果没有巴基斯坦的同意，本·拉丹是不可能回到阿富汗的。巴基斯坦军事情报机构很可能事先获得了本·拉丹到来的消息，其官员也很可能为本·拉丹的顺利出行提供了方便。本·拉丹在苏丹的整个期间，都一直在巴基斯坦和阿富汗保留着住所和训练营。这些地方，包括塔吉克斯坦、克什米尔和车臣，都是各种组织用来招募新兵、训练战士，准备伊斯兰暴动的大系统的一部分。据说巴基斯坦情报官员将本·拉丹介绍给在坎大哈的塔利班领导人，以帮助他恢复对科斯特附近的营地的控制，其目的是希望本·拉丹扩充营地，从而使之能够有效训练克什米尔的斗士。但本·拉丹处在反抗前苏联战争以来实力最弱的时期。苏丹政府撤销了本·拉丹开设在苏丹的大量企业的登记，后来还将其中一些公开拍卖。根据“基地”一名高级受羁押人的说法，苏丹政府没收了本·拉丹在那里拥有的一切。
本·拉丹还失去了“基地”军事委员会的头目。阿布·乌贝达·艾尔·班西瑞是“基地”组织能力最强，也最受欢迎的领导人之一。当小组的大多数关键人物与本·拉丹一道去往阿富汗时，班西瑞则留在肯尼亚，对4年前设在那里的基层组织的训练和武器运输工作进行监督。在本·拉丹到达贾拉拉巴德以后没几天，班西瑞在维多利亚湖一次渡船事故中丧生。由此，本·拉丹不仅需要在伊斯兰武装咨询委员会中寻找替代班西瑞的人，而且还需要寻找在东非监督基层组织及其将来活动的人。在其他方面，本·拉丹也需要作些调整，因为有些“基地”组织成员将本·拉丹回到阿富汗当做他们开小差的机会。一些人保持着与“基地”组织的合作关系，但是更多的人完全处于游离状态。
本·拉丹一度无法确定塔利班是否是他进行联盟的最好赌注。在本·拉丹到达阿富汗以后，塔利班控制了这个国家的大部分地区，但是关键的中心区域，包括喀布尔，还处在敌对军阀的掌控之中。本·拉丹最初去了贾拉拉巴德，这很可能是因为它是一个由伊斯兰领导人组成的省级地方议会控制的地区，这些领导人并非国家权力的有力竞争者。本·拉丹与主要“圣战”派系之一的头目——杨尼司·卡哈里斯同住。很显然，本·拉丹依然处在选择之中。他与古尔布德丁·海克马特亚保持着联系，后者是一个伊斯兰极端分子，同时也是塔利班的最富有战斗精神的对手之一。但在1996年9月，贾拉拉巴德和喀布尔先后陷入塔利班的控制以后，本·拉丹加强了与这些人的联系。
但这个过程并不总是一帆风顺的。不再受苏丹人约束的本·拉丹认为他完全有号召人们投入“圣战”的自由。大约在塔利班对贾拉拉巴德和喀布尔进行最后的大规模强攻时，本·拉丹发表了他的1996年8月“圣战宣言”。他说：“我们……曾经被禁止向穆斯林发表讲话。”但是他又宽慰地说：“以真主的光荣，一个安全的‘基地’已经建立，它位于呼罗珊的印度库什山上。”但是塔利班与苏丹人一样，最终听从了包括沙特阿拉伯国王在内的人提出的警告。
虽然本·拉丹向塔利班作出了保证，他会谨慎行事，但他几乎立即就违背诺言。1997年3月，他向CNN发表了煽动性的谈话。塔利班领导人穆拉赫·奥马尔迅速“邀请”本·拉丹转移到坎大哈去，这从表面上看是为了本·拉丹的个人安全，但事实上是将他置于更易被控制的境地。
另有证据显示，本·拉丹在这段时间里还派出大量侦察人员到伊拉克，提出与伊拉克政权合作。据说没有人得到伊拉克方面的明显回应。根据一份报告，此时萨达姆正努力与沙特阿拉伯和其他中东政权重建关系，这使他与本·拉丹保持着距离。
1998年中期，形势发生了改变，据说伊拉克这次采取了主动。1998年3月，在本·拉丹的公开“反美圣战宣言”发表以后，据说两名“基地”组织成员去伊拉克与伊拉克情报人员会面。7月，伊拉克的一个代表团到达阿富汗，先会见了塔利班，后会见了本·拉丹。有线人称，其中一次会见或两次会见显然是由本·拉丹的一名埃及代表扎瓦西里安排的，扎瓦西里本人与伊拉克有联系。1998年，伊拉克处在美国的强大压力之下，这种压力以12月份的一系列空中袭击而达到顶点。
伊拉克官员与本·拉丹或其助手在1999年也进行了类似的会面。据说在这段时间，本·拉丹与塔利班的关系有些紧张。据报道，伊拉克官员提出，伊拉克会给本·拉丹提供一个安全的避难所。本·拉丹拒绝了，显然他认为他此时在阿富汗的处境要比选择去伊拉克后的处境更为有利。该报道叙述了双方的友好接触，并且在憎恨美国问题上有共识。然而我们至今没有证据表明双方早期或者此时的接触最终发展成合作行动关系，也没有证据显示伊拉克与“基地”组织一起开展或采取了反对美国的袭击行动。
