The document, "Norway - Last 30 days", shows that between December 12th last year and January 8th, 33,186,042 calls were registered in the country.
"Friends should not monitor each other," Norway's prime minister Erna Solberg told Norwegian broadcaster NRK on Tuesday. "It is legitimate to engage in intelligence, but it should be targeted and suspect based."
"It is unacceptable for allies to engage in intelligence against eachother's political leadership," added justice minister Anders Anundsen.
Jens Stoltenberg, Norway's prime minister at the time the surveillance reportedly took place, said that he had not been informed of the monitoring when he grilled senior US officials on data collected from Norway after the first NSA revelations in June.
"I have not been informed of the sort of monitoring which is now being described," he told NRK. "The information that is now coming out shows that it is necessary to go a second round with the Americans. It is important to get the facts and then evaluate them."
The US Embassy in Oslo refused to comment on the revelations: "When it comes to intelligence activity, we can not comment on individual cases. The United States collects intelligence overseas, as every nation does."
Norway is the sixth country to learn details of phone data collected by the NSA, following the decision of Edward Snowden, an IT contractor with the agency, to make public the scale of the its surveillance.
Documents leaked by Snowden, who is now in exile in Russia, have shown the scale of phone data collected by the agency in Germany, France, Spain, Brazil and India.
The NSA did not record the content of the 33 million Norwegian calls, but stored 'meta data', such as the length of the calls, the phone numbers of the caller and the call recipient, where the phone was located, and the serial numbers of the phones.
The head of NIS, Norway's intelligence service, Lieutenant General Kjell Grandhagen, told Dagbladet that his agency had not collaborated with US to collect the data, and had been unaware that it was being collected.
According to Dagbladet, Norwegian phone companies NetCom and Telenor both deny giving the NSA access to their systems.
Torstein Olsen, head of Norway's telecoms regulator, said that it was illegal for anyone apart from telecommunications companies to collect such data.
"If Dagbladet's information is correct that 33 million mobile phone calls in Norway were registered by someone other than the telecommunication companies, that would be a crime under Norwegian law," he said.
According to Bård Vegar Solhjell, a senior minister in Stoltenberg's government, American officials claimed during meetings in June and July that there was no such illegal surveillance of Norwegians.
"They said that all intelligence was gathered in compliance with Norwegian law and American laws. We were given an assurance that there was no illegal surveillance of Norwegians," he said.
Bjørn Erik Thon, the head of Norway's data protection agency, said that even after nearly six months of the Snowden leaks, he was surprised.
"The number is very high: if ten percent of all calls in Norway are monitored, we cannot talk about targeted surveillance," he said. "It would not been been allowed even if it had been targeted, but it is even more serious when it goes to this extent."
Norway is one of the '9-eyes' network of countries which share intelligence closely with the US. The group adds Denmark, France, Norway and the Netherlands, to the 5-eyes group of the US, UK, Canada, New Zealand and Australia.