Sweden's intelligence service Säpo discovered in 2009 that two Americans were conducting illegal, under-cover investigations in Sweden, the Svenska Dagbladet (SvD) daily reported.
The two men were discovered when Säpo noticed them tracking people who it was also investigating for suspected ties to terrorist groups, the paper said, quoting several unnamed sources close to Säpo.
Washington had not informed Swedish authorities of the agents' activities in the country, and soon after their activities were discovered, the two US citizens left the country, the paper added.
Referring to Washington's failure to inform Pakistan before it tracked and killed Osama bin Laden three weeks ago, Svenska Dagladet insisted "the US has also carried out intelligence against terrorists on Swedish territory.
"Sweden has thus become the scene of a foreign power's terror hunt without the knowledge of the Swedish government," it said.
Säpo could not be reached late Sunday. Head of the agency Anders Danielsson refused to comment when confronted by the paper.
Following the report, US embassy spokesperson Christopher Dunnett stressed the importance of cooperation between the United States and Sweden.
"We have excellent cooperation with Swedish authorities in a several areas, including anti-terror activities," he told the TT news agency on Monday morning.
He refused to elaborate, however, on the allegations of unauthorised spying.
"We don't comment on security issues in detail," he said.
Neither justice minister Beatrice Ask nor foreign minister Carl Bildt were willing to comment on the matter Sunday night.
Speaking on Monday, prime minister Fredrik Reinfeldt said he wasn't aware of the details surrounding the US agents' alleged activities in Sweden.
"I don't want to speculate on information in the media because we have very independent agencies in Sweden which operate in their respective areas of responsibility," he told TT.
"I want to note that in this case the responsible agency hasn't confirmed or denied (the report)."
Reinfeldt didn't expect to pursue the matter further and emphasised that Sweden has a solid and close cooperation with the United States.
If the report about the unauthorised US spying is true, it amounts to a serious allegation, according intelligence expert professor Wilhelm Agrell.
"There's no support for this in international law. What's problematic is running an operation like this without going through the Swedish authorities," he told the TT news agency.
According to Agrell, it's more common for "less friendly states" to carry out unauthorised intelligence activities against exile groups, for example.
At the same time, he's not surprised that the United States would do the same thing.
"It's been common practice for the Americans since September 11th, 2001 to carry out operations both with and without consent from the country where the operation takes place," he said.
Legal scholar Dennis Töllborg said it was "incredibly strange" that the CIA reportedly chose not to follow normal procedures by allowing Säpo to conduct surveillance on the suspected terrorists.
However, he doesn't think that the CIA's alleged decision to go behind Säpo's back indicates that the US spy agency lacks confidence in agents from its Swedish counterpart.
"I believe more that after 9/11, the CIA has given itself rights which don't have any limits at all, here and everywhere," he told TT.
Töllborg added that he doubts the incident has damaged CIA-Säpo relations, but more that it amounts to an embarrassment for the Americans.
The new revelations cover operations different from the US embassy's Surveillance Detection Unit (SDU) which was the focus of an investigation by Sweden's top prosecutor after reports surfaced in the media suggesting that the unit may have engaged in unlawful intelligence gathering.
However, prosecutor Tomas Lindstrand dropped the probe in early April because he was unable to gather sufficient evidence to substantiate the allegations.