Shannon Stapleton/Reuters

LOUISVILLE, Ky.—Republicans took the Senate majority in a commanding sweep on Tuesday, winning nearly every contested race across the country, gaining governor's mansions and adding to their majority in the House of Representatives. For weeks, pundits had debated the semantics of what would constitute a "wave" election, but when it came, it was unmistakable.

Republicans unseated Democratic incumbents in Senate races in Arkansas, North Carolina, and Colorado, and were leading in Alaska early Wednesday. They easily held onto GOP-controlled seats in Georgia, Kansas, and Kentucky. In New Hampshire, Democrat Jeanne Shaheen barely held on against Republican Scott Brown. In one of the night's biggest surprises, Virginia Senator Mark Warner, who was thought to be safe, was up only half a point over his Republican challenger early Wednesday. The Louisiana election, in which Democrat Mary Landrieu finished slightly ahead of her Republican challenger, Bill Cassidy, was set to go to a December runoff, which Cassidy is favored to win.

Though Pennsylvania's abysmally unpopular Republican governor, Tom Corbett, was defeated, Republicans took over governor's mansions in Arkansas, Illinois, Maryland, and Massachusetts, and were leading by a hair in Colorado. Controversial Republican incumbents Scott Walker (Wisconsin), Rick Snyder (Michigan), Sam Brownback (Kansas), Paul LePage (Maine), Nathan Deal (Georgia), and Rick Scott (Florida), all of whom had appeared vulnerable in pre-election polls, all held on to win reelection.

Ebullient Republicans, many of whom had run relentlessly one-note campaigns focused on the unpopular president, touted the results as a rejection of President Obama and Democratic policies. "This race wasn't about me or my opponent," Mitch McConnell, the Kentucky senator who easily won reelection and stands to become the new majority leader, told a ballroom full of supporters here. "It was about a government people no longer trust."

Much speculation now focuses on McConnell, who has been blamed for singlehandedly stopping most of the Obama agenda for the past five years. (Ironically, the conservatives who want the Obama agenda stopped give McConnell little credit for doing so.) But McConnell now faces a choice about whether continued obstruction will serve his party's interests. In his victory speech, he mentioned no specific policies but rather struck a conciliatory note.

"Some things don't change after tonight," he said. "I don't expect the president to wake up tomorrow and view the world any differently than he did when he woke up this morning, and he knows I won't either. But look, we do have an obligation to work together on issues where we can agree. Just because we have a two-party system doesn't mean we have to be in perpetual conflict."

The new Senate majority will mean the ascension of McConnell, a master politician who does not excel at the more public parts of the job—much like the outgoing majority leader, Harry Reid of Nevada. And it means the fall of Reid, who has led the majority since 2007, keeping a diverse caucus remarkably unified while changing the Senate rules and, Republicans complain, preventing most bills and amendments from being considered.

McConnell will now have his own fractious caucus to corral, starting with the junior senator in his own state, Rand Paul, who spoke from the same stage Tuesday night. Paul spoke of a sharply conservative agenda for the new Senate: tax cuts, balancing the budget, approving the Keystone XL pipeline, and "repealing every last vestige of Obamacare." McConnell will face pressure from conservatives like Paul and Ted Cruz of Texas to pursue a maximally confrontational approach—as Paul put it, sending Obama "bill after bill" and daring him to veto them all. On the other hand, Senate GOP pragmatists—likely including those just elected from blue states and those who face reelection in 2016—want the new majority to seek constructive compromise in order to prove to voters that Republicans can govern.