Spain delivered the message to US Ambassador James Costos, summoned to explain the latest revelations in a growing scandal over US snooping on telephone and online communications of ordinary citizens and world leaders including German Chancellor Angela Merkel.
The news emerged just as a European Parliament delegation was to begin a three-day mission to Washington to probe the impact of the surveillance on EU citizens' "fundamental rights" and to discuss a request to suspend an EU-US agreement on the transfer of bank data in the wake of the scandal.
Spanish foreign ministry officials met with the US envoy hours after daily newspaper El Mundo published a classified document purportedly showing that the US security services tracked 60.5 million Spanish telephone calls in a single month.
The National Security Agency recorded the origin and destination of the calls and their duration but not the content, said El Mundo, which printed a classified graph showing 30 days of telephone call tracing up to January 8 this year.
The graph illustrated the daily volume of calls traced in the period, peaking at 3.5 million on a single day, December 11.
Though not shown on the graph, the newspaper said such systematic trawling of huge volumes of digital information -- or metadata -- would include intercepting personal details through Internet web browsers, emails and social networks such as Facebook and Twitter.
The article was jointly authored by US blogger Glenn Greenwald, who said he had access to previously secret documents obtained by former US intelligence contractor Edward Snowden.
The Spanish foreign ministry said it had underscored with the US ambassador its concern over the reported snooping.
"Spain conveyed to the United States the importance of preserving the climate of trust that governs bilateral relations and of knowing the scale of practices that, if true, are inappropriate and unacceptable between countries that are partners and friends," it said in a statement.
Spain's state secretary for the European Union, Inigo Mendez de Vigo, "urged the US authorities to provide all necessary information about the supposed tapping in Spain", it said.
The US ambassador said in a separate statement that some of the security programmes played a "critical role" in protecting Americans and were also instrumental in protecting allied interests.
He promised to work diplomatically to address Spain's concerns.
El Mundo said it had reached an agreement with Greenwald for exclusive access to Spain-related spying documents leaked by Snowden.
The paper urged Spanish prosecutors to charge the NSA with spying, saying such tracing of telephone calls without the proper judicial authority amounted to a criminal offence.
Prime Minister Mariano Rajoy said after a summit with fellow European Union leaders in Brussels on Friday that he had no evidence that Spain had been spied on.
At the summit, the 28 European Union leaders approved a statement which said they valued the relationship with the United States but it had to be based on trust and confidence, especially in intelligence matters.
France and Germany are to lead efforts to reach a new understanding with Washington by the end of this year.
The Wall Street Journal said Monday that the NSA had tapped the phones some 35 world leaders including close ally Merkel, who last week branded the snooping as unacceptable between friends.
President Barack Obama learned of the espionage programme only after an internal mid-year review,and the White House then ordered an end to the spying on some leaders, including Merkel, the Wall Street Journal said.
NSA spokeswoman Vanee Vines flatly denied reports in Germany that NSA chief General Keith Alexander had briefed Obama on the operation against Merkel in 2010 but that the president let the spying continue.
German media had reported at the weekend that eavesdropping on Merkel's phone may have started in 2002, when she was Germany's main opposition leader and three years before she became chancellor.
And the daily Bild am Sonntag quoted US intelligence sources as saying that Obama himself had been informed of the phone tap against Merkel by NSA chief General Keith Alexander in 2010 but allowed it to continue.
Alexander "did not discuss with President Obama in 2010 an alleged foreign intelligence operation involving German Chancellor Merkel, nor has he ever discussed alleged operations involving Chancellor Merkel," Vines said Sunday.
"News reports claiming otherwise are not true."