The National Security Agency monitored the phone conversations of 35 world leaders after being given the numbers by an official in a separate US government department, according to a classified document which was provided by whistle-blower 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" Merkel's communications. Officials in Berlin quickly pointed out that the US did not deny monitoring the phone in the past.
At a European Union leaders summit in Brusselfs yesterday, Merkel and French President Francois Hollande insisted the US agree upon new surveillance rules with them this year to stop eavesdropping on their leaders, civilians and companies.
"We are seeking a basis for co-operation between our [intelligence] services, which we all need and from which we have all received a great deal of information ... that is transparent, that is clear and is in keeping with the character of being partners," Merkel said.
The German government said senior officials from its intelligence agencies would travel to the US "shortly" for talks about the allegations.
Yet EU leaders vowed to maintain a strong trans-Atlantic partnership. Hollande said "what is at stake is preserving our relations with the United States". He insisted that "trust has to be restored and reinforced".
The memo provided by Snowden - a former NSA contractor - suggests that surveillance such as that alleged by Merkel was not isolated, as the agency routinely monitors the phone numbers of world leaders.
The 2006 memo - issued to staff in the agency's Signals Intelligence Directorate (SID) - was titled "Customers Can Help SID Obtain Targetable Phone Numbers".
It highlights 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 centres] have noted 43 previously unknown phone numbers. These numbers plus several others have been tasked." The document adds new phone numbers had helped the agency discover still more new contact detailsto 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". Despite this, the memo then asks analysts to think about any "customers" 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!"
Obama administration officials declined to respond directly to the new material.
Additional reporting byAssociated Press