At the time, the United States didn't want Bin Laden either, since he hadn't yet been tied conclusively to any crimes committed against U.S. citizens or on U.S. soil. So on May 18, 1996, Bin Laden flew to the eastern Afghan city of Jalalabad.
It was a very different Afghanistan that Bin Laden came back to. For years, the mujahedin factions that had forged an uneasy alliance against the Communists had been making war on one another. The country was in ruins, and millions had lost their homes and livelihoods.
A fanatical militia, the Taliban, was capturing more and more territory. Covertly funded by Pakistani and Saudi intelligence, this band of puritans imposed draconian edicts, banning shaving for men, women's education, and amusements such as music.
Astute about the changing realities, Bin Laden visited Kabul in October 1996 after the Taliban occupied it, and held parleys with the group's leadership. They reportedly got along famously.
The Taliban's success in defeating or bribing enemies might have happened without Bin Laden's participation. But he gave the group a valuable shot in the arm by putting up or raising money to finance military campaigns and furnishing dedicated Arab fighters to spearhead the Taliban's assaults.
To curry favor with the Taliban's supreme leader, a one-eyed son of poor Pashtun farmers named Mullah Mohammed Omar, Bin Laden built him a house. He showered other Taliban dignitaries with money and presents.
In return, the Taliban-held lands, which came to include almost all of Afghanistan, became a haven and launch pad for Bin Laden and his version of holy war. He reportedly helped fund and train terrorists for Pakistan who could be infiltrated into Kashmir, the disputed Himalayan region claimed by both India and Pakistan.
In Afghanistan, Bin Laden found valuable new human assets and allies, including dozens of exiled Egyptian extremists who became a key part of Al Qaeda's expanding core.
These associates included Ayman Zawahiri, founder of the Egyptian Islamic Jihad, and Mohammed Atef, a former policeman who was its military commander.
The merger of Al Qaeda and Egyptian Islamic Jihad created a terrorist force of great ambition and destructive power.
In addition to supporting Al Qaeda with contributions from what was left of his personal fortune, Bin Laden funded the group through criminal enterprises such as drug trafficking and extortion and money skimmed from legitimate Islamic charities.
In 1997, the Taliban uncovered what it said was a Saudi plot to assassinate Bin Laden, and for his own protection, he moved into an old Soviet air base outside Kandahar, the Taliban stronghold in the country's south.
Bin Laden worked assiduously to unify the numerous and diverse radical Islamic movements under Al Qaeda's banner, exploiting his reputation, money and charm to draw other leading figures.
In 1998, along with Zawahiri and extremists from Pakistan and Bangladesh, he issued the fatwa in the name of the "International Islamic Front for Jihad against Jews and Crusaders" that called killing Americans and their allies was a sacred duty for Muslims.
In August 1998, a colossal bomb destroyed the U.S. Embassy in Nairobi. At almost the same time, a second bomb rocked the U.S. Embassy in Dar es Salaam. One suspected was arrested, he later told FBI agents that he had fought in Afghanistan with the Taliban and was handpicked by Bin Laden for the bombing mission.
In a pattern that had become familiar, Bin Laden issued a statement welcoming the bombings, which had killed many Muslims.
Secret, spartan life
The now-stateless Bin Laden's day-to-day life was described to the Observer, the British newspaper, by a defecting Al Qaeda associate in June 1999.