(CNN) -- In a vote that could have implications on the November presidential race, Wisconsin Gov. Scott Walker successfully overcame a recall vote Tuesday that would have removed him from office.

The big night for Republicans had a sliver of a possible silver lining for Democrats, who may have picked up one state Senate seat, which would tip control to the Democratic Party. But the legislature will be out of session until after the general election in November.

Democratic Mayor Tom Barrett of Milwaukee conceded defeat to Walker in a recall attempt triggered by the governor's push to reform collective bargaining rights of public sector employees to reduce state spending.

"I just got off the phone with Gov. Walker and congratulated him on his victory tonight. We agreed that it is important for us to work together," he said.

Walker gave a triumphant victory speech Tuesday night, thanking many for helping him survive the recall effort.

"Tonight, we tell Wisconsin, we tell our country and we tell people all across the globe that voters really do want leaders who stand up and make the tough decisions," he told a roaring crowd at his campaign headquarters in Waukesha.

He also addressed the polarized climate in the normally centrist state -- his crowd jeered when he mentioned that he had a phone conversation with Barrett before taking the stage.

"Bringing our state together will take some time -- there's just no doubt about it," he said.

Wisconsin Lt. Gov. Rebecca Kleefisch, also a Republican, will hold on to her office, CNN projected.

Four Republican senators faced recall votes Tuesday as well. At least three held on to their seats. But Sen. John Lehman, a Democrat, declared victory in ousting incumbent Sen. Van Wanggaard. The vote was extremely close, and results have not been certified, CNN affiliate WTMJ reported.

"It is clear that we won the 21 district," Lehman told cheering supporters

The recall effort against Walker was spurred by a law he backed and signed in March 2011 to limit the collective bargaining rights of state worker unions.

The AFL-CIO in Wisconsin worked in favor of the recall.

"We wanted a different outcome, but Wisconsin forced the governor to answer for his efforts to divide the state and punish hardworking people. Their resolve has inspired a nation to follow their lead and stand up for the values of hard work, unity, and decency that we believe in," the statement said. "We hope Scott Walker heard Wisconsin: Nobody wants divisive policies"

The vitriolic campaign included tens of millions of dollars in funding from outside the state, mostly for the Republican governor.

The victory by the first-term governor may give Republicans a major boost in efforts to make Wisconsin a battleground state in the November presidential election.

Presumptive GOP nominee Mitt Romney called Walker to offer his congratulations.

"Governor Walker has demonstrated over the past year what sound fiscal policies can do to turn an economy around, and I believe that in November voters across the country will demonstrate that they want the same in Washington, D.C. Tonight's results will echo beyond the borders of Wisconsin," Romney said in a statement.

President Barack Obama easily won the state in 2008, but Walker's unyielding commitment to fiscal austerity made him the poster child for tea party conservatism.

Obama's campaign released a statement praising those who worked on the recall.

"While tonight's outcome was not what we had hoped for -- no one can dispute the strong message sent to Governor Walker," the statement said. "Hundreds of thousands of Wisconsinites from all walks of life took a stand against the politics of division."

Leading up to the Tuesday vote, both candidates took jabs at each other.

Walker complained that repeated recall efforts over past years were stalling progress and costing the state needed money.

In conceding, Barrett drew catcalls when he mentioned the call with Walker. And he said it was important that he and the governor work together.

But he urged his supporters to fight on.

"This is not an end," he said. "Tonight ends another chapter in Wisconsin history, but there's more to come."

A local woman was not amused by Barrett's concession speech, with video from CNN affiliate WISN showing her slapping the mayor after the speech.

The woman asked Barrett if she could slap him for conceding while voting was still under way, the affiliate reported. Barrett said he'd rather she hug him, but when he leaned down, the woman slapped him instead, according to the affiliate.

The race has been marked by high tensions.

During a bitter fight over the law last year, Democratic legislators left the capital to prevent a quorum, and tens of thousands of protesters converged on the State Capitol building in what became an occupation.

After the law was signed, Democrats immediately began a recall effort that led to Tuesday's vote.

Walker defended his budget actions as necessary for the fiscal health of his state and described his campaign as one of a strong leader who is making the necessary "tough decisions."

The campaign was fierce, with campaigners complaining of keyed cars, verbal harassment and a general lack of tolerance for differing opinions.

"We have an example of Hatfields and McCoys going on in this state like we have never seen," said Brian Nemoir, a Milwaukee-based Republican strategist. "People are hyper-engaged, as much in support for their own candidate as in disgust for the opponent."

A litany of Republican stars campaigned for Walker, including fellow Govs. Chris Christie of New Jersey, Nikki Haley of South Carolina, Bobby Jindal of Louisiana and Bob McDonnell of Virginia, as well as U.S. Sen. Marco Rubio from Florida.

Barrett, meanwhile, got his own high-powered support from former President Bill Clinton, as well as Democratic National Committee Chairwoman Debbie Wasserman Schultz and Maryland Gov. Martin O'Malley.

Obama never came to Wisconsin to campaign for Barrett, which Republicans surmised was because the president thought Barrett would lose.

On Sunday, Barrett said on CNN's "State of the Union" that his campaign never asked Obama to appear on his behalf, adding that "we understand he's got a lot going on."

White House press secretary Jay Carney acknowledged the uniqueness of the contest while stressing there's no doubt where the president stands.

"The president's made clear all along his opposition to those who would take away workers' rights -- to actions that would take away or diminish workers' rights," he said. "And he's also made clear his support for Tom Barrett."

CNN's Peter Hamby, Samuel Gardner III and Dana Bash contributed to this report.