Feinstein said her committee will begin a "major review into all intelligence-collection programs," The Wall Street Journal reported.
"Congress needs to know exactly what our intelligence community is doing," she said.
"Unlike NSA's [National Security Agency's] collection of phone records under a court order, it is clear to me that certain surveillance activities have been in effect for more than a decade and that the Senate Intelligence Committee wasn't satisfactorily informed. Therefore our oversight needs to be strengthened and increased."
The California Democrat also said she expected the White House would quit spying on the leaders of its allies, including German Chancellor Angela Merkel, the newspaper said. White House spokesman Jay Carney said during his daily briefing with reporters that Obama has "made clear that we do not and will not monitor the chancellor's communications."
The Journal said U.S. officials disclosed the NSA stopped spying on several world leaders, including Merkel, after a White House review came across the program. The spying allegedly went on for years without the president's direct knowledge, something Feinstein told the newspaper she sees as "a big problem."
Carney said while the U.S. intelligence community has done an extraordinary job of foiling terrorist plots, the rapid advances in technology used to gather the information led Obama to order a review of U.S. surveillance capabilities this past summer.
"This review is being led by the White House, and it includes agencies from across the government," Carney said. "Our review is looking across the board at our intelligence gathering to ensure that as we gather intelligence, we are properly accounting for both the security of our citizens and our allies, and the privacy concerns shared by Americans and citizens around the world.
"We also need to ensure that our intelligence resources are most effectively supporting our foreign policy and national security objectives, that we are more effectively weighing the risks and rewards of our activities. And that includes ensuring that we are focused, above all, on threats to the American people. Once again, as you've heard the president say, we need to ensure that we are collecting information not just because we can, but because we should, because we need it for our security."
The Spanish government summoned the U.S. ambassador Monday regarding allegations the NSA amassed data on millions of phone calls in Spain.
After meeting with Spanish officials, Ambassador James Costo, in a statement, acknowledged Spain's concerns and said, "Ultimately, the United States needs to balance the important role that these programs play in protecting our national security and protecting the security of our allies with legitimate privacy concerns."
Neither Costo nor Spanish government officials discussed details of the spying claims, The New York Times reported.
In a separate statement, Inigo Mendez de Vigo, Spain's secretary of state, discussed the need to maintain "a necessary balance" between security and privacy concerns.
Spain called on Washington to clarify "the reach of measures that, if proven to be true, are improper and unacceptable between partners and friendly countries," Mendez said.
Two Spanish newspapers -- El Mundo and El Pais -- reported Monday the NSA collected data on 60 million phone calls in Spain, adding Spain to the list of countries where the United States is accused of monitoring communications.
The two newspapers' reporting was based on documents provided by former NSA contractor Edward Snowden, who has been at the center of the spying scandal.
The Spanish newspapers said the NSA collected data on phone numbers and locations but did not monitor the contents of the calls. The data covered information for about 60 million Spanish phone calls and was collected from December to early January.
The halt to the phone tapping on about 35 world leaders came after the existence of such surveillance appeared in an internal Obama administration review that was started during the summer, the officials told the Journal.
Other programs scheduled to end have yet to be phased out completely, officials said.
The newspaper's account -- the administration's first public acknowledgment it tapped world leaders' phones -- suggests President Barack Obama went nearly five years without knowing the spying was going on, the Journal said.
The NSA said in a statement agency Director Keith Alexander "did not discuss with President Obama in 2010 an alleged foreign intelligence operation involving ... Merkel, nor has he ever discussed alleged operations involving ... Merkel. News reports claiming otherwise are not true."
The NSA did not say in its statement whether anyone else had briefed Obama on the spying.
Obama knew about and approved broader intelligence-collection "priorities," but didn't decide about specific intelligence targets, the officials said.
"These decisions are made at NSA," the senior U.S. official told the Journal. "The president doesn't sign off on this stuff."
That protocol is now under review, the official said.