Mohammed Umr remembered when he last heard from the sheikh. He was crouched in a cave high in the Tora Bora mountains in easternAfghanistan in December 2001. Huge bombs dropped by American B-52s shook the ground around him. A thousand feet below, Afghans loyal to the Northern Alliance and squads of US and British special forces were climbing the steep lower slopes.

On the radio, the young Afghan heard Osama bin Laden‘s distinctive voice. “He told us that a great struggle had started and that we were going to retreat so as better to fight another time,” Umr told the Guardian in an interview in Kabul in August 2008. “I left with a hundred others. The sheikh stayed behind. I do not know where he went.”

On Sunday the 54 year-old Saudi-born leader of al-Qaida was killed by aCIA team in the Pakistani town of Abbottabad, barely 150 miles (240km) east of the mountain stronghold of Tora Bora which, ten years before, had been his last confirmed location. That he was found so close to where he had left the few hundred militant fighters he had rallied as theTaliban regime in Afghanistan collapsed underlines the complexities and challenges of the hunt for the mastermind of the 9/11 attacks.

That hunt started well before the battle at Tora Bora. Though barely noticed by western security services while he supported Afghan mujahideen in their struggle against the Soviets from bases in Afghanistan in the 1980s, reports that Bin Laden received cash from the CIA are false: the Saudi began to concern American intelligence agencies from the early 1990s.

First they thought his role was limited to funding militancy but as information came in from stations around the world, a more threatening profile came together. “We realised he was a much more serious player than we had thought,” said Jack Cloonan, an FBI agent seconded to the CIA to help build a case against Bin Laden in 1996. A series of bellicose declarations and then the bombings of east African US embassies in 1998 left no further doubt. Cloonan and others, such as Michael Scheuer, who headed the CIA Bin Laden unit, pressed for more resources and action from the administration of Bill Clinton but were ignored. “People thought we were touched in the head,” said Scheuer.

Nevertheless a series of operations to capture Bin Laden were planned – and then cancelled at the last minute. Cloonan was once even tasked to read the militant leader his legal rights – a scenario which, given the events in Abbottabad on Sunday, seems extraordinary.

Meanwhile, the CIA and the state department worked to strengthen the Afghan opposition led by legendary guerilla leader Ahmad Shah Massoud.

Few doubted the threat posed by Bin Laden, but their efforts were too little too late. As the useless missile attacks in the Sudan and Afghanistan in the aftermath of the 1998 embassy bombings had shown, the American political and military establishment lacked the tools and the practical understanding to tackle the problem. New plans were hatched by the incoming Bush administration but never implemented. Then came 9/11 and everything changed.

In the immediate aftermath, Bin Laden was a key target for the American special forces soldiers and CIA operatives infiltrated or air-dropped into Afghanistan. But no one knew where to look for him and it was only after the collapse of the Taliban following two months of bombing that the hunters – CIA units and special forces – began to close in. Bin Laden had been seen near Kandahar in the run up to the 9/11 strikes – one last act was to hand out development money for a well in a local village – then had moved up to Kabul during the war before finally fleeing towards his old haunts near the eastern city of Jalalabad, where he had been based intermittently since returning to Afghanistan from Sudan in 1996.

When Kabul fell, he and several hundred followers – including the young fighter Mohammed Umr – had retreated in the cave and bunker complex Bin Laden had helped construct over a decade earlier during the war against the Soviets in Afghanistan. The al-Qaida group had been founded in 1988 in Peshawar, the Pakistani frontier city. Tora Bora, as the hills around the cave complex was known, was home ground. It was where he knew he could disappear.

The combat at Tora Bora was a good deal more chaotic than usually described. It was more a fighting retreat than a pitched battle. Militants were fleeing north, south, east, following trails into Pakistan all along the border with Pakistan and, for some, into Iran. Recent American interrogation reports of local Afghan militants who were at the battle indicate a poorly armed force, scrabbling for ammunition and medical supplies under heavy bombardment. Bin Laden appears to have left in some haste, possibly heading north, through the lines of the special forces and their Afghan auxiliaries and escaping into the wild regions of north-east Afghanistan before looping back into Pakistan.

Throughout 2002 and 2003, a series of major al-Qaida figures were picked up, largely thanks to intercepted communications. These included the mastermind of the 9/11 plan itself, Khalid Sheikh Mohammed. Significantly, given where Bin Laden was eventually killed, they were found in major cities such as Karachi and Rawalpindi. Co-operation between the CIA and the Pakistanis – especially the ISI military intelligence service – was relatively good, according to Rob Grenier, the then-CIA station chief.

By 2003, General Pervez Musharraf, the then-president of Pakistan was sending tens of thousands of troops into the tribal zones along the Afghan-Pakistan frontier, increasing pressure on the fugitives. With the Taliban dispersed or dead, the training camps defunct and the money flows shut down, al-Qaida in south-west Asia seemed on the run even if violence was exploding across the Middle East and into Europe.

When US military officials proposed in 2002 that special operations forces be allowed to establish bases in the tribal areas, the Pakistanis flatly refused – one row was over whether they could carry American weapons or only local AK47s – but an early arrangement allowed American commandos to join Pakistani units on raids inside the tribal areas and a new joint operations centre, staffed by Pakistani, American and other western intelligence officers, was set up in Islamabad. Hundreds of other militants were rounded up and handed over to the Americans – often for “bounties” totaling millions of dollars paid to the Pakistani government.

With new resources and manpower, and a new spirit of co-operation among American agencies, there was “a general confidence” that Bin Laden would be soon caught or killed, said Bruce Riedel, then a senior director at the CIA. “There was a feeling that we were closing in.”

One encouraging sign was the arrest of Yassir al-Jazeeri, a Moroccan believed to be one of Bin Laden’s closest bodyguards, in March 2003. This was one of the earliest interceptions of a courier and showed a key vulnerability: Al-Jazeeri had a handwritten note from Bin Laden in his pocket. The militant leaders’ carefully low-tech communication systems – couriers carrying notes – was not as secure as they thought.

In retrospect, though, 2003 marked a high point because things got much harder very quickly. Detainees at Guantánamo Bay prison camp told their captors of meetings in Shakai, a remote wilderness area close to the Pakistani border with Afghanistan. Already deeply hostile to outside interference, the people of the rugged mountains and valleys along the 1,500-mile frontier had become steadily more radicalised over the previous years. The arrival in late 2001 of hundreds of hardened fighters from Afghanistan – including the Taliban leadership – had led to a new radicalism. The $25m reward offered for Bin Laden provoked no leads among the fierce Pashtun tribal populations among whom he lived. It was not just the traditional melmastia – or customary duty of hospitality – which meant Bin Laden found a welcome, but also an increasing link between a belligerent, centuries-old Pashtun tribal identity and a much newer globalised Islamic identity that were responsible.

Fear – and a vast cultural gulf between the hunters and potential informers – also played a part. “Al-al-Qaida would often buy security by dumping a large amount of cash on local notables who in turn keep their people in line, so the chances of being killed for someone who gave us information would be considered high”‘ said Arthur Keller, a former CIA man posted to the tribal areas between 2005 and 2006. According to Mahmood Shah, a senior Pakistani official who ran security in the seven semi-autonomous tribal agencies that line the frontier, threats to the militants’ growing power were brutally eliminated as “spies”. Hundreds were to be executed over the years.

In the anarchy fostered by two decades of war, traditional structures of authority had been overturned. Tribal chiefs no longer had the respect they once had – and were easy victims for aggressive young leaders for whom extremist jihadi ideology was a useful way of legitimising brutality and theft. A debate among intelligence analysts over whether Bin Laden and his key associate Ayman al-Zawahiri were staying in one spot or moving between hiding places, whether they were together or apart, seemed academic.

Whether they were hunkered down in a compound or constantly mobile, whether in good or poor health, the three million inhabitants of the Tribal areas were a solid wall around Bin Laden that neither the Pakistani army, the ISI nor the CIA could break.

The American effort faced other problems too. Crucial assets such as surveillance drones and personnel – some of whom had spent 18 months learning the ground – had been diverted to Iraq. “By April, May 2002, we began losing people to the groups that were preparing for the Iraq war,” said Scheuer, who after heading the CIA’s Bin Laden unit from 1996 to 1999 was its chief adviser from 2001 to 2004. “We were losing Arabic speakers. Very experienced people.”

The US military’s elite commando unit, Delta Force, had been transferred out of Afghanistan. So too had the 5th Special Forces Group, which included the best linguists, and was replaced in Afghanistan by a unit largely composed of Spanish speakers with mostly Latin American experience. The CIA case officers with tribal contacts were rotated out. The result was that “we ended up with the best and the brightest chasing the wrong man in the wrong desert,” said former senior CIA officer Riedel.

The hunt for Bin Laden got the “barrel scrapings,” in Keller’s words, who himself had just two months to prepare for his stint in Pakistan. At Langley, Virginia, the CIA headquarters, Keller learned of a further reason for the slow progress: problems with the Pakistanis which in turn had led to divisions within the CIA itself. “No one wanted to go to Pakistan. Partly because it’s not a particularly nice place but also because of all the complaints about working with the Pakistanis,” he said.

“The Pakistanis just did not move. We had all these resources on offer for them. But they were extremely passive. It was deeply frustrating for everybody,” Keller said. Another frustration was the impossibility of getting out on the ground – even for the most important leads. “I had someone who believed he had information on the location of High Value Target One [Bin Laden] but I could only communicate with him through encrypted messages. We only met once and that was several weeks later,” Keller said.

The CIA did have “assets” of their own and therefore did not entirely rely on technology – itself far less potent than most imagine: American spy satellites were not sensitive enough to pick up mobile phones so listening posts were needed on the ground instead. The result was little direct intelligence. “We had our guys who would speak to us directly. The Pakistanis had their guys and would pass on information,” Keller said. But Pakistani co-operation was only forthcoming when it concerned “internationals” – the Arabs and other foreigners connected to al-Qaida – not the local or Afghan Taliban.

Interviewed by the Guardian, ISI officers protested that their problem was the terrain, their own bureaucracy – and western pressure. Officers from the service regularly briefed foreign counterparts, using a comprehensive PowerPoint presentation to push home the point that they were operating in a hostile land where simple geography posed huge problems. The message was clear: not finding Bin Laden was not their fault. The ISI officers said that, despite aid to the armed forces amounting to around $100m (£60m) a month, the Pakistani army was still desperately short of resources for counter-terrorism. And the Americans had little leverage. “The ISI was the only girl at the dance,” said a senior CIA official later transferred to the FBI.

By the middle of the decade, any relationship that did exist had deteriorated sharply. With levels of anti-American feeling reaching historic highs, any co-operation with the USA presence caused uproar in Pakistan and massive political pressure on Musharraf.

A string of operations by the Pakistani army on the frontier revealed a lack of will and capacity for the fight. The international militants had little difficulty in escaping, relying on the local Pakistani Taliban groups which emerged during this period to keep the Pakistani military and their allies at bay. Bin Laden himself maintained a low profile – a lull in video and audio announcements even fuelling rumours that the militant leader might have died of kidney disease. This was just one of many false alarms.

And, as the hunt began to run out of steam, reminders began to arrive of just how important catching Bin Laden and breaking up the al-Qaida organisation still was. One had come in 2004 with the Madrid bombings – not directly linked to Bin Laden but inspired by his rhetoric. Then in 2005 came the attacks on London. The investigation into the 7/7 bombings, as well as that into the ammonium nitrate plot that had been broken up in the UK a few months earlier, revealed that al-Qaida had been able to re-establish itself in the Pakistani tribal zones. So too did the Walthamstow plot of 2006, which targeted airlines over the Atlantic. The terrorist groups’ infrastructure was a pale shadow of what it had been before 2001 in Afghanistan but nonetheless allowed them to operate relatively effectively, albeit in a more diffuse and chaotic fashion than before.

A steady flow of increasingly professional videos and audio cassettes left the tribal zones or were posted on the internet. Volunteers and cash from wealthy donors in the Gulf and elsewhere flowed into the mountains even though senior militants often complained if the financial support was insufficient. The money was useful to buy any tribesmen whose support was wavering – or pay for others to be killed. The volunteers were also useful to maintain good relations with the Afghan Taliban, who launched their own major offensive in 2006 or – particularly in the case of the scores of British Pakistani recruits who made their way into the zone – to launch attacks in the west.As the investigations into the 7/7 bombings and other plots that followed in 2006 and 2007 showed, the latter could easily be convinced that the greatest contribution they could make to the jihad was not to fight with the Taliban but to return home and strike the ‘far enemy’. Western intelligence agencies became more and more concerned at the role of the tribal areas – “the grand central station of modern militancy”, in the words of one British intelligence service source speaking in 2007.

Yet, though various militants were captured or killed, Bin Laden remained so elusive that some began to think that he was dead. Nigel Inkster, deputy director of MI6 until 2006, told the Guardian there was not a single solid piece of information precisely locating either Bin Laden or Zawahiri throughout this period. To complicate matters further, the watchers needed “real-time intelligence” which would tell them where either man would be in at least four hours’ time and which was necessary to activate the cruise missiles and scramble the special forces teams waiting to go in. But every time rumours of the al-Qaida leaders’ deaths seemed credible, one or other would resurface.

Operation after operation was cancelled as departments rowed over levels of risk for troops or collateral damage and political fallout. First, a plan in late 2005 for a special operations mission to capture Bin Laden’s close associate Zawahiri in what would have been the most aggressive use of US ground troops inside Pakistan was abandoned for fear of provoking a violent political reaction locally. Then in early 2006 a complex plan put together by the American Department of Defence Intelligence services that involved flying special forces on microlight planes to attack a compound a few miles from the Pakistan-Afghan border, where Zawahiri was thought to be was abandoned at the very last minute after frenzied exchanges between officials at the Pentagon, US military Central Command and the CIA. A missile strike instead destroyed half a village, killing a number of militants and several civilians.

Throughout late 2007 and early 2008 the situation deteriorated further. In Afghanistan, a resurgent Taliban were tying down more and more American resources. And with serious question marks over the integrity of the ISI and mounting evidence of the Pakistani security establishment’s support for the newly resurgent Taliban, relations between the Pakistanis and the Americans got even worse. Rows broke out between CIA stations in Pakistan and Afghanistan over the exact role of the Pakistani secret services in the violence across the border and the degree to which they were protecting militants. The hunt for Bin Laden became more and more embroiled in the struggle against the Taliban – and against the newly formed Pakistani Taliban.

Speaking in late 2007, as fierce battles raged across half of Pakistan’s North-West Frontier province pitting the Pakistani army against a variety of militant groups, one US defence source in Islamabad spoke of targeting lower-level militants as a key strategy to “work back up to the big guys”. The source admitted that it was suspected that the ISI were helping certain Taliban factions, if not the international terrorists. In London, concern rose about the steady stream of young Britons finding their way to the tribal areas, often facilitated by hardline Pakistani groups. “Some dozens” fought with the Taliban, according to one UK intelligence source. Others were sent back to the UK.

Bin Laden and Zawahiri were still thought to be in the tribal areas, possibly moving from place to place, possibly simply hidden somewhere in the mountains, forests and valleys of Shakai. Yet a steady stream of intelligence – often from captured European or other volunteers who returned to their homes after training or fighting with al-Qaida or other groups – gave intelligence services a better picture of what was happening in the restive border regions.

First of all they learned of the sheer variety of groups in the Federally Administered Tribal Areas (FATA). Arriving volunteers came via Pakistani groups with representation in the tribal zones or made their way under their own steam, chosing which faction to join when they got there. One told American and Belgian investigators of Turkish, Uzbek and a range of different Arab groups, all coexisting in various zones of the FATA. There was the shifting coalition of the Pakistani Taliban, various Afghan groups, the insurgents of the Pashtun war lord and cleric Jalaluddin Haqqani to whom the ISI had “channels of communication,” MI6 told the Guardian.

The returning volunteers also gave an indication of life in the FATA. Several were very disappointed not to have ever seen Bin Laden or taken part in the kind of training they had seen in videos or on the internet. They complained of being “deceived” to their handlers who told them bluntly the propaganda was designed to impress enemies and potential recruits and did not reflect reality. Conditions were tough too – with rudimentary medical attention and poor food. Under pressure financially, al-Qaida made recruits pay for their own equipment and rent, provoking further protests. Others, however, were excited to be crossing into Afghanistan with the groups al-Qaida sent to aid and instruct the Taliban. Some even remembered – among the paranoia induced by the intensifying zone attacks – moments of relaxation, going for walks in the wooded valleys between raids.

Bin Laden remained invisible . Even the freshest information of his whereabouts dated back to the middle of the decade.

As relations with the ISI sank into mutual recrimination and insult, partly as a result of further detailed reporting of Pakistani backing for insurgents in Afghanistan, then-president George W Bush decided to cut the Pakistanis out of the chain. In the dying months of his presidency, ignoring the state department and ceding to the hawks in the department of defence and the CIA who were pushing for a more aggressive strategy, senior Bush administration officials had drafted a secret plan to make it easier for the Pentagon’s special operations forces to launch missions into the snow-capped mountains of Pakistan to capture or kill top leaders of al-Qaida. Until 2006, missile strikes needed to be signed off by the ISI and by the American ambassador in Islamabad. By late 2008, the American intelligence agencies primarily involved in the hunt for Bin Laden – particularly defence intelligence and the special forces they commanded – waited neither for Pakistani permission nor for the green light from US diplomats even if the strike involved lower level operatives. In the late summer, the outgoing president had sanctioned the attacks in one of the last acts of his administration. It proved to be a turning point.

For the first time, too, US military personnel began crossing the porous frontier from Afghanistan. A village was hit by special forces coming from the west. Missile strikes into Pakistan increased in intensity. New drones arrived, redeployed from Iraq. Military planners even began sketching out a new strategy to send spies into Pakistan from the Afghan side of the border, rather than in the other direction. The final phase of the hunt for Bin Laden had commenced, and all the various elements which had been so out of line previously fell slowly into place.

One major change had been on the Pakistani side. By the autumn of 2008, the damage that international jihad could do to Pakistan was becoming very clear. Local militants were becoming more radical, following al-Qaida’s teaching that the Pakistani state should be a target. It was Pakistani groups that had killed Benazir Bhutto in December 2007 but they had been influenced – possibly even funded – by the foreigners living amongst them.

Musharaf was forced out of his role as military head with the dry, moderate, severe and efficient Ashfaq Kayani taking over. Bhutto’s widower, Asif Ali Zardari, had been the man who took power as president when Musharaf was finally ousted in August 2008 and had a much less ambivalent relationship with the militants than his predecessor.

A huge bomb in Islamabad in September of that year and rising attacks on military installations and personnel convinced the political and the military leadership of the country that, whatever the popular sentiment, serious action needed to be taken. Better-armed, better-trained forces were sent in large numbers into areas which had been seized by the militants.

One of the first to fall was Bajaur, the northernmost tribal agency and a key logistics node for al-Qaida. Steadily, the militants were squeezed. Back in 2003, the al-Qaida leadership had been forced out of the Pakistani cities and up to the mountains. Last weekend it appeared that in recent years a similar process had occurred – just in reverse.

Growing anger among the tribesmen of the FATA at the destruction the conflict brought to their villages was also a factor. The solidarity that had once existed in the face of the infidel aggressor began to fall apart. Many of the Pakistani militants were from socially marginalised backgrounds, had little clerical training and no claim to traditional authority. Communities began to shift their allegiances.

The trail that led the CIA to Bin Laden appears to have begun with the arrest of a key lieutenant, Abu Faraj al-Libbi in the northern Pakistani town of Mardan in May 2005. Detained by the ISI and handed over to the Americans, recently leaked documents prepared for Guantánamo Bay tribunals show that Libbi gave his interrogators the names of a series of couriers. “One courier in particular had our constant attention,” an American official said yesterday. He declined to give that courier’s name but said he was a protege of Khalid Sheikh Mohammed and a “trusted assistant” of Libbi.

The official added that other unnamed detainees also “identified this man as one of the few couriers trusted by Bin Laden” . This corroboration may well have come from Abdul Hadi al-Iraqi, another very senior al-Qaida operative who was arrested in 2007. The official said that the US intelligence community had uncovered the crucial identity of this courier four years ago.

Also, confidential documents released by WikiLeaks revealed that Abdul Hadi had been a source of considerable amounts of information. He too was filling the role of al-Qaida’s “director of external operations”, a vulnerable post with a short life expectancy because it necessitated exposure outside the closed security circle around the top leadership names, and would have known about the couriers.

But the information clearly took time to be turned into actionable intelligence. To launch a successful operation, specific intelligence was required on where the target will be in four hours’ time. This was still lacking. Around 2009 apparently, the US discovered roughly the area of Pakistan where the courier and his brother were working. Finding the home where Bin Laden had been hiding with his family took longer. In the intervening period, though the relations between Pakistan and the US continued to see-saw, the areas where Bin Laden could hide were being further restricted as the army pushed into new areas.

In August 2010, the intelligence agencies found the exact compound where this courier was living, in Abbottabad. That home was in an affluent suburb of a nondescript garrison town, perhaps selected for its very anonymity and, of course, its good communications and ease of access to the tribal zones.

“When we saw the compound where the brothers lived, we were shocked by what we saw,” one official said.

The compound was eight times larger than the other homes around it. It had been built in 2005 in an area that was secluded at that time. There were extraordinary security measures at the compound, including 3-5 metre-high walls topped with barbed wire.

They realised immediately this was no normal residence. Access to the compound was severely restricted. The main part of the residence had three floors but had few windows. It was worth hundreds of thousands of dollars but, crucially, had no phone or internet connection.

Adding to intelligence agencies’ suspicions was that the two brothers had no known source of income. The CIA learned, too, that there was a family living with them and that this family matched the profile of Bin Laden’s.

By February, the CIA was confident this was Bin Laden’s likely hiding place and in March, Barack Obama began chairing a series of national security meetings. These met twice in March and three times last month. At the last of these, on 29 April, he gave the order to mount an operation. The long hunt was over.

Jason Burke, the Guardian’s south Asia correspondent, is the author of Al-Qaeda: The True Story of Radical Islam