This chapter covers Osama bin Laden’s return to Afghanistan in 1996 and the start of the al-Qaida-Taliban relationship. When bin Laden returned to Afghanistan in May 1996, he was initially looking for a refuge from where he could continue his proselytizing campaign against the Saudi regime. He found refuge in Eastern Afghanistan with old allies from the Afghan-Soviet war. When Taliban came to power a few months later, and invited bin Laden to stay under their protection, bin Laden saw an opportunity to continue the state-building project he had failed to finish in Sudan. An internal al-Qaida document from 1997 outlines the first contours of al-Qaida’s Afghanistan strategy: Taliban-run Afghanistan would be an exemplary Islamic state and a base from where to spread the Islamic revolution. Like Sudan, Afghanistan was situated on the fringes of the Muslim world, far from the US influence that prevented al-Qaida from establishing a base in the Middle East.