Yet Bin Ladin was in his weakest position since his early days in the war against the Soviet Union. The Sudanese government had canceled the registration of the main business enterprises he had set up there and then put some of them up for public sale. According to a senior al Qaeda detainee, the government of Sudan seized everything Bin Ladin had possessed there.⁶⁸

He also lost the head of his military committee, Abu Ubaidah al Banshiri, one of the most capable and popular leaders of al Qaeda. While most of the group's key figures had accompanied Bin Ladin to Afghanistan, Banshiri had remained in Kenya to oversee the training and weapons shipments of the cell set up some four years earlier. He died in a ferryboat accident on Lake Victoria just a few days after Bin Ladin arrived in Jalalabad, leaving Bin Ladin with a need to replace him not only in the Shura but also as supervisor of the cells and prospective operations in East Africa.⁶⁹ He had to make other adjustments as well, for some al Qaeda members viewed Bin Ladin's return to Afghanistan as occasion to go off in their own directions. Some maintained collaborative relationships with al Qaeda, but many disengaged entirely.⁷⁰

For a time, it may not have been clear to Bin Ladin that the Taliban would be his best bet as an ally. When he arrived in Afghanistan, they controlled much of the country, but key centers, including Kabul, were still held by rival warlords. Bin Ladin went initially to Jalalabad, probably because it was in an area controlled by a provincial council of Islamic leaders who were not major contenders for national power. He found lodgings with Younis Khalis, the head of one of the main mujahideen factions. Bin Ladin apparently kept his options open, maintaining contacts with Gulbuddin Hekmatyar, who, though an Islamic extremist, was also one of the Taliban's most militant opponents. But after September 1996, when first Jalalabad and then Kabul fell to the Taliban, Bin Ladin cemented his ties with them.⁷¹