WASHINGTON (AP) — Eight days after blocking it, Senate Republicans have agreed to begin debate on a House bill that would overhaul the National Security Agency's handling of American calling records while preserving other domestic surveillance provisions.

But that remarkable turnabout didn't happen soon enough to prevent the laws governing the programs from expiring at midnight Sunday as Republican Sen. Rand Paul, a presidential contender, stood in the way of extending the program, angering his GOP colleagues and frustrating intelligence and law enforcement officials.

Now, the question is whether the Senate will pass a bill the House can live with. If so, the surveillance programs will resume, with some significant changes in how the phone records are handled. If not, they will remain dormant.

The Senate vote on the measure known as the USA Freedom Act can come no earlier than 1 a.m., Tuesday. Senate Republican aides said they expected some amendments, but no major revisions to the bill.

"Having gone past the brink, the Senate must now embrace the necessity of acting responsibly," said Adam Schiff, the ranking Democrat on the House intelligence committee, in a statement after Sunday's Senate vote.

The high-stakes drama played out as Congress debated the most significant changes prompted by the disclosures of Edward Snowden, the former NSA contractor who revealed the phone records collection and other main surveillance programs. With no deal reached in time, the NSA stopped collecting American phone records at 3:59 p.m. EST Sunday, officials said.

Other authorities that expired allowed the FBI to collect business records in terrorism and espionage investigations, and to more easily eavesdrop on a suspect who is discarding cell phones to avoid surveillance.

Intelligence officials publicly warned of danger, but were not deeply concerned with a lapse of a few days or weeks, given that the authorities remain available in pending investigations. What they most fear is a legislative impasse that could doom the programs permanently.

"The Senate took an important_if late_step forward tonight," White House spokesman Josh Earnest said in a statement. "We call on the Senate to ensure this irresponsible lapse in authorities is as short-lived as possible."

President Barack Obama supports the USA Freedom Act, which ends NSA bulk collection of U.S. phone records but allows the agency to search records held by the phone companies. That bill, which preserves the other expiring provisions, passed the House overwhelmingly May 13.

Senate Republicans blocked that legislation on May 23, arguing that it undercut the NSA's ability to quickly search the records. It fell three votes short of the 60 needed to advance.

But with no other options, Senate Majority Leader Mitch McConnell, in an about-face, reluctantly embraced the House-passed bill Sunday night.

"It's not ideal but, along with votes on some modest amendments that attempt to ensure the program can actually work as promised, it's now the only realistic way forward," McConnell said.

The Senate then voted 77-17 to move ahead on the USA Freedom Act.

McConnell was boxed in by the actions of his fellow Kentucky Republican, Paul, who helped stymy the leader's attempt to pass an extension of current law. Paul objected each time McConnell attempted to bring that measure to a vote.

Paul opposes the USA Freedom Act as not going far enough. But, he predicted , the USA Freedom Act "will ultimately pass."

Earlier, in a fiery speech decrying NSA surveillance, he shouted, "This is what we fought the revolution over, are we going to so blithely give up our freedom? ... I'm not going to take it anymore." Supporters wearing red "Stand With Rand" T-shirts packed the spectator gallery.

Paul's moves infuriated fellow Republicans and they exited the chamber en masse when he stood up to speak after the Senate's vote on the House bill.

Sen. John McCain, R-Ariz. complained to reporters that Paul places "a higher priority on his fundraising and his ambitions than on the security of the nation."

Paul, for his part, asserted that, "People here in town think I'm making a huge mistake. Some of them I think secretly want there to be an attack on the United States so they can blame it on me."

Civil liberties groups were split. Some, including the ACLU, oppose the USA Freedom Act as too weak, and applauded the expiration of the surveillance laws. If the USA Freedom Act passes, the NSA would resume bulk phone records collection during a six month transition period to the new system.

"Congress should take advantage of this sunset to pass far-reaching surveillance reform, instead of the weak bill currently under consideration," said Michael Macleod-Ball, acting director of the ACLU Washington Legislative Office.

But that seemed unlikely. Liberal senators who have been aggressive in criticizing the NSA are backing the USA Freedom Act.

"I'm pleased Republicans joined with Democrats to do what's responsible and support the passage of the USA Freedom Act," said Sen. Martin Heinrich, a New Mexico Democrat. "This is a bipartisan compromise that would ensure that our intelligence community has the tools it needs to focus more narrowly on the records of actual terrorists, and end the bulk collection of law-abiding Americans' private phone calls."