But a handful of privy lawmakers in Congress were not surprised at all. One of those was Sen. Ron Wyden (D-OR), who along with his colleagues on the Senate Intelligence Committee had been secretly briefed on the program years prior to the program's leaking.
About fifteen minutes after the story broke, Wyden received another call on his cell phone.
"I can't tell you what you want me to tell you!," he told the caller. It was Wyden's former communications director Jennifer Hoelzer, who had spent more than half a decade by the senator's side. It wasn't news to her that her former boss had known about the secret program, but she was surprised that he was still barred from confirming or denying its existence.
By the end of the first hour -- approaching midnight -- press officers for the members on the Senate Intelligence Committee were unable to comment to journalists on the record about a program that they, as non-clearance holding staffers, weren't even aware of themselves.
"There was an incredible amount of fear and panic, because nobody knew what else was coming," said a senior congressional official with direct knowledge of the events on that and subsequent days, who declined to be named for this story.
"Nobody knew how sensitive these leaks were, and whether or not this was the sort of thing that would put individuals at risk," the person said. There was a strong suspicion that the leaker was someone within the intelligence community -- perhaps someone high up in the chain of command with access to internal intelligence documents. There was a scramble among those with security clearance to find out what had been leaked, and who might have leaked it.
Sens. Dianne Feinstein (D-CA) and Saxby Chambliss (R-GA) released a joint statement first thing the next morning on June 6 as the American people were reading the news over their morning coffee. The statement said that members of Congress had been "briefed extensively" on the program.
Except, that wasn't entirely true.
Some members of the Senate Intelligence Committee later admitted they weren't even aware of the full scope of the program. Sens. Angus King (I-ME) and Susan Collins (R-ME), who joined the committee months before the Snowden disclosures, told one local newspaper a day after news of the leaks broke that they had not known "specifics" of certain surveillance programs, including the phone records program.
In his statement, Wyden doled out his critical rhetoric, saying that he had been "concerned" for years about the program. He also said the program's effectiveness was "unclear."
Wyden's former chief of staff Josh Kardon, who served for more than a decade between 1996 and 2010, explained that prior to the leaks the senator was clued up because he wouldn't just rely on what the intelligence officials were telling him.
Kardon said the senator would "develop his own sources" within the intelligence community instead of relying on the White House to give him straight answer.
By law, the intelligence agencies have to keep the committee (and other key leadership-holding members of Congress) informed of their activities, but they would instead drip feed information and hope nobody asked too many follow-up questions. Things were so bad, said a former staffer close to Wyden who did not want to be named for the story, that the senator could have asked the simplest of questions, like "if anybody had the time," to which an intelligence agent would respond with, simply, "yes."
A day after the first leak, a second surveillance program -- known as PRISM -- was revealed.
The secret program was met with instant backlash from Silicon Valley after it was shown to allow the collection of almost every shred of user information held by nine named technology giants. Inside the walls of Congress, that panic had turned to anger at the inability to speak out.
It was clear by now that the first leak was not an isolated incident. It would be a guessing game as to what would come next -- even to those who thought they were in the know.
This is part two in a series of reports based on interviews, conducted over a period of eight months, with lawmakers and their staffers, policy-makers, security leaders, and key figures who have played a role in the NSA surveillance saga.