The National Security Agency monitored the phone conversations of 35 world leaders after being given the numbers by an official in another US government department, according to a classified document provided by whistleblower Edward Snowden.
The confidential memo reveals that the NSA encourages senior officials in its "customer" departments, such as the White House, State and the Pentagon, to share their "Rolodexes" so the agency can add the phone numbers of leading foreign politicians to their surveillance systems.
The document notes that one unnamed US official handed over 200 numbers, including those of the 35 world leaders, none of whom is named. These were immediately "tasked" for monitoring by the NSA.
The revelation is set to add to mounting diplomatic tensions between the US and its allies, after the German chancellor Angela Merkel on Wednesday accused the US of tapping her mobile phone.
After Merkel's allegations became public, White House press secretary Jay Carney issued a statement that said the US,
"is not monitoring and will not monitor" the German chancellor's communications.
But that failed to quell the row, as officials in Berlin quickly pointed out that the US did not deny monitoring the phone in the past.
Arriving in Brussels for an EU summit Merkel accused the US of a breach of trust.
"We need to have trust in our allies and partners, and this must now be established once again. I repeat that spying among friends is not at all acceptable against anyone, and that goes for every citizen in Germany."
The NSA memo obtained by the Guardian suggests that such surveillance was not isolated, as the agency routinely monitors the phone numbers of world leaders - and even asks for the assistance of other US officials to do so.
The memo, dated October 2006 and which was issued to staff in the agency's Signals Intelligence Directorate (SID), was titled "Customers Can Help SID Obtain Targetable Phone Numbers".
It begins by setting out an example of how US officials who mixed with world leaders and politicians could help agency surveillance.
"In one recent case," the memo notes, "a US official provided NSA with 200 phone numbers to 35 world leaders…
Despite the fact that the majority is probably available via open source, the PCs [intelligence production centers] have noted 43 previously unknown phone numbers. These numbers plus several others have been tasked."
The document continues by saying the new phone numbers had helped the agency discover still more new contact details to add to their monitoring:
"These numbers have provided lead information to other numbers that have subsequently been tasked."
But the memo acknowledges that eavesdropping on the numbers had produced "little reportable intelligence".
In the wake of the Merkel row, the US is facing growing international criticism that any intelligence benefit from spying on friendly governments is far outweighed by the potential diplomatic damage.
The memo then asks analysts to think about any customers they currently serve who might similarly be happy to turn over details of their contacts.
"This success leads S2 [signals intelligence] to wonder if there are NSA liaisons whose supported customers may be willing to share their 'Rolodexes' or phone lists with NSA as potential sources of intelligence," it states. "S2 welcomes such information!"
The document suggests that sometimes these offers come unsolicited, with US "customers" spontaneously offering the agency access to their overseas networks.
"From time to time, SID is offered access to the personal contact databases of US officials," it states. "Such 'Rolodexes' may contain contact information for foreign political or military leaders, to include direct line, fax, residence and cellular numbers."
The Guardian approached the Obama administration for comment on the latest document. Officials declined to respond directly to the new material, instead referring to comments delivered by Carney at Thursday's daily briefing.
Carney told reporters:
"The [NSA] revelations have clearly caused tension in our relationships with some countries, and we are dealing with that through diplomatic channels.
"These are very important relations both economically and for our security, and we will work to maintain the closest possible ties."
The public accusation of spying on Merkel adds to mounting political tensions in Europe about the scope of US surveillance on the governments of its allies, after a cascade of backlashes and apologetic phone calls with leaders across the continent over the course of the week.
Asked on Wednesday evening if the NSA had in the past tracked the German chancellor's communications, Caitlin Hayden, the White House's National Security Council spokeswoman, said:
"The United States is not monitoring and will not monitor the communications of Chancellor Merkel. Beyond that, I'm not in a position to comment publicly on every specific alleged intelligence activity."
At the daily briefing on Thursday, Carney again refused to answer repeated questions about whether the US had spied on Merkel's calls in the past.
The NSA memo seen by the Guardian was written halfway through George W Bush's second term, when Condoleezza Rice was secretary of state and Donald Rumsfeld was in his final months as defence secretary.
Merkel, who, according to Reuters, suspected the surveillance after finding her mobile phone number written on a US document, is said to have called for US surveillance to be placed on a new legal footing during a phone call to President Obama.
"The [German] federal government, as a close ally and partner of the US, expects in the future a clear contractual basis for the activity of the services and their co-operation," she told the president.
The leader of Germany's Green party, Katrin Goring-Eckhart, called the alleged spying an "unprecedented breach of trust" between the two countries.
Earlier in the week, Obama called the French president François Hollande in response to reports in Le Monde that the NSA accessed more than 70m phone records of French citizens in a single 30-day period, while earlier reports in Der Spiegel uncovered NSA activity against the offices and communications of senior officials of the European Union.
The European Commission, the executive body of the EU, this week backed proposals that could require US tech companies to seek permission before handing over EU citizens' data to US intelligence agencies, while the European parliament voted in favor of suspending a transatlantic bank data sharing agreement after Der Spiegel revealed the agency was monitoring the international bank transfer system Swift.