Five days after 9/11, early on a Sunday evening, a small group of senior CIA officers drove from their headquarters in Langley, Virginia, to the British embassy at 3100 Massachusetts Avenue NW in Washington DC, in order to brief MI6 on the agency’s planned response to the attacks.

Leading the delegation was Cofer Black, head of the CIA’s counter-terrorist centre. Black was still wearing the same suit he had put on five days earlier, and looked shattered: he had been working day and night to draw up a cogent plan to protect his country from any further attacks.

Inside the embassy, Black and his colleagues gave a three-hour presentation on their plans. The CIA had been running a kidnap-and-interrogation project on a small scale since the mid-90s, targeting jihadists in Bosnia. It was known as the rendition programme. The plan was to dramatically increase the scale and scope of the programme.

According to Tyler Drumheller, then head of CIA operations in Europe, the MI6 officers listened quietly as Black detailed his plan, which involved the identification, abduction and interrogation of al-Qaida suspects around the globe. At the end of the presentation, Mark Allen, head of counter-terrorism at MI6, observed rather dryly that “it all sounds rather blood curdling”. Drumheller noted that the MI6 officers appeared very worried. Some of his fellow CIA officers, with less experience of dealing with the Brits, mistook their slightly insouciant manner for a sign of approval.

Allen wanted to know what the CIA and MI6 would do after al-Qaida was scattered across the world. He asked: “And what are we going to do, once we have hammered the mercury in Afghanistan?” The CIA officers looked at each other. According to one account of the meeting, Black said: “We’ll probably all be prosecuted.”

The death toll of the 9/11 attacks was still rising and President George W Bush was eager to take a tough stance. The day after the Pentagon briefing, Bush gave a press conference in which he offered a glimpse of what was to come. “I want justice,” he said. “There’s an old poster out west that says: ‘Wanted – Dead or Alive.’”

The implications of this would be thrashed out early the following year by the heads of the intelligence agencies of the US, UK, Canada, New Zealand and Australia. At a meeting at Queenstown, a ski resort in New Zealand, CIA director George Tenet insisted they could only understand and defeat al-Qaida if they worked closely with intelligence agencies across the Muslim world, and if they agreed to do whatever it took to hit back against terrorists. “The shackles, my friends, have been taken off,” Tenet is said to have declared.

One of the most pressing imperatives was to create close ties with the intelligence agencies of the Arab world. With this aim, in 2002 the CIA and MI6 began co-operating with the Libyan External Security Organisation (ESO), Col Muammar Gaddafi’s notorious overseas intelligence agency.

The stated agenda was to learn more about militant Islamism, but that would change the following year once Allen and his British political masters saw an opportunity to enter into negotiations with Gaddafi over his programme to develop weapons of mass destruction. Gaddafi had been trying to develop nuclear capability since the early 1970s, initially by trying to acquire Indian-made weapons, and then by attempting to gain access to uranium ore and enrichment technology.

From the late summer of 2003, as the war in Iraq began to go badly for the US and its allies, it became increasingly clear that Saddam Hussein’s weapons of mass destruction – the WMD programme that officially justified the invasion of Iraq – did not exist. But if Gaddafi could be persuaded to abandon his own nuclear plans, those who had pressed for war against Iraq could claim the invasion had been vindicated.

As the CIA and MI6 built relationships with Libya, the two agencies assisted Libyan spies in the kidnapping of Gaddafi’s enemies. Two leading figures in the Libyan opposition who had fled the country were kidnapped, one from Hong Kong, one from Thailand, and flown back to Tripoli along with their wives and children. Both men were tortured. MI6 gave their Libyan counterparts questions for the prisoners, who, under extreme duress, led them to other Libyan dissidents in exile.

In early 2003, as US and UK forces mustered on the borders of Iraq, Gaddafi was afraid they would target Libya. According to one diplomat, he called the Italian prime minister, Silvio Berlusconi, begging him to “tell them I will do whatever they want”.

In March, Blair secured the backing of the Commons for war against Iraq, and two days later the invasion began. Three weeks after that, Baghdad appeared to have fallen to the US and the war was thought to be all but over: on 1 May, on board the aircraft carrier USS Abraham Lincoln, Bush gave an address in front of a large banner declaring: “Mission Accomplished.”

The secret papers show that by then Allen was regularly meeting with a senior CIA officer, Stephen Kappes, to discuss ways they could make sure Gaddafi abandoned his ambitions to develop nuclear, chemical and biological weaponry. During their conversations with Koussa, no sanctions were threatened; there was little need, as all three men knew Gaddafi was terrified of being invaded by the US. At meetings in Tripoli, MI6 officers discussed not only the WMD programme, but ways of targeting Libyan “heretics” around the world. British intelligence officers told the Libyans they had intercepted Sami al-Saadi’s telephone calls from his home in Tehran.