"The choice in this election is not about regions or religions or genders," Obama said. "It's not about rich versus poor, young versus old and it's not about black versus white. It's about the past versus the future."
Fueled by strong support among blacks and younger voters, Obama trounced both New York Sen. Hillary Clinton and former North Carolina Sen. John Edwards.
Obama spoke to a raucous group of supporters and was slated to head to Georgia late Saturday to campaign in that Feb. 5 state.
"The cynics who believed that what began in the snows of Iowa was just an illusion were told a different story by the good people of South Carolina," he said.
Obama outpolled Clinton 78 percent to 19 percent among blacks, a group that made up nearly half of voters in the primary. Among white voters, Clinton and Edwards each garnered nearly four in 10 voters, with Obama getting nearly 25 percent.
"We are looking for more than just a change of the party in the White House," Obama said.
South Carolina politicians, past and present, who backed Obama hailed the result.
"This was a first-round knockout," former Gov. Jim Hodges, who endorsed Obama, told South Carolina Educational Television. "It was a broad coalition that pushed Barack Obama over the top... He has answered his critics who have said he cannot build a broad racial coalition and he has done it in a deep southern state."
Obama echoed the sentiment, saying, "We have the most votes, the most delegates and the most diverse coalition of Americans we've seen in a long, long time."
Record turnout throughout the state helped Obama, especially in the northern counties.
"Barack Obama is bringing new people into the process, young people, people turned off by politics and I think those people really turned out today," Brad Warthen of The State newspaper told SCETV.
Exit polls indicated that Obama continued to score support of younger voters, garnering 50 percent of 18- to 29-year-olds.
"If this victory matches the exit polls and he wins this state by 30 points, it is an enormous victory," Meet the Press' Tim Russert said. "He can say he put together a winning coalition."
In the days before the vote, Clinton argued that Obama would win in the state because of support from black voters.
"[Obama] ran as a Democratic candidate for president who happens to be black, not as the black candidate. And the Clinton campaign set out deliberately... to make him the black candidate," Mark Shields said on Friday's NewsHour. "Bill Clinton is already into a pre-spin about the South Carolina result. And it reads this way: 'They tell me Hillary can't win down here because blacks are going to support Barack Obama overwhelmingly.'"
That campaign tactic appeared to have an impact Saturday. Nearly six in 10 voters said the former president's efforts for his wife influenced their choice; among them, slightly more favored Obama than Hillary Clinton.
Obama took a thinly veiled swipe at the Clintons during his speech.
"We are up against the idea that it's acceptable to say anything and do anything to win an election," Obama said. "We know that this is exactly what's wrong with our politics; this is why people don't believe what their leaders say anymore; this is why they tune out. And this election is our chance to give the American people a reason to believe again."
But whatever the role of former President Clinton, Obama's support appeared to be widespread. Overall, Obama defeated Clinton among both men and women.
The political victory was Obama's first since he won the kickoff Iowa caucuses on Jan. 3. Clinton scored an upset in the New Hampshire primary a few days later. They split the Nevada caucuses, she winning the turnout race, he gaining a one-delegate margin. In a historic race, she hopes to become the first woman to occupy the White House while Obama is the strongest black contender in history.