Democratic White House hopeful Hillary Clinton defied pundits and pollsters by winning New Hampshire's primary, beating rival Barack Obama.
John McCain made his own remarkable political comeback with a comfortable win in the Republican contest.
In a night of high political drama, turnout was nearly half a million - more than double the number in 2004.
Candidates are aiming to build momentum before more than 20 states hold polls on 5 February, known as Super Tuesday.
New York Senator Clinton, 60, told CNN on Wednesday morning: "I really believed that I had a very good chance - nobody else believed it - but I did, and I'm very grateful to the people of New Hampshire for giving me that victory last night."
Her rebound echoed that by her husband, former President Bill Clinton, who in New Hampshire's primary of 1992 called himself the "comeback kid" when his own faltering White House bid was resurrected by a strong, second place finish in the state.
Polling station interviews suggested female voters, who deserted Mrs Clinton last week in Iowa, and registered Democrats helped sweep her to victory, overcoming Senator Obama's advantage among New Hampshire's independent voters.
Mr Obama, a 46-year-old first-term senator from Illinois, said: "I want to congratulate Senator Clinton on a hard fought victory. She did an outstanding job."
He had gone into the vote with leads of up to 13 points in opinion polls following his impressive win in Thursday's Iowa caucuses, having trailed Mrs Clinton for much of the campaign.
BBC diplomatic correspondent Jonathan Marcus says the stage is now set for a remarkable toe-to-toe fight for the Democratic nomination.
The contest will pit the experience and financial muscle of the Clinton campaign against the Obama camp's transformational message, says our correspondent.
Clinton aides said her win may be down to an extraordinary moment on Monday when she appeared close to tears as she talked about how much public service meant to her.
John Edwards, who came third in the Democrat contest, reminded supporters in Manchester, New Hampshire, that there were "48 states left to go".
In the Republican race, Arizona Senator McCain rode to victory, taking 37% of the vote to beat his higher spending rival Mitt Romney into second place with 32%.
Ex-Arkansas governor and Baptist minister Mike Huckabee and former New York mayor Rudy Giuliani came in with 11% and 9% of the vote for the Republicans.
Triumph for Mr McCain, a 71-year-old former Vietnam prisoner of war who has promised voters to "follow Osama Bin Laden to the gates of hell", put him firmly back in contention for the White House, said correspondents.
He thanked his supporters, saying: "My friends, you know I'm past the age where I can claim the noun 'kid', no matter what adjective precedes it. But tonight we sure showed 'em what a comeback looks like."
Mr McCain had been the front-runner until his campaign ran out of steam last year when his funds and support evaporated, analysts said, down to his unflinching support for the Iraq war.
Former Massachusetts governor Mr Romney congratulated Mr McCain and said: "Well another silver... I'd rather have a gold, but I got another silver.
The BBC's James Coomarasamy in New Hampshire says a wounded Mr Romney must now bounce back from his Iowa and New Hampshire defeats, states where he far outspent his opponents.
KEY DATES AHEAD
15 Jan: Michigan primary
19 Jan: Nevada caucuses; South Carolina primary (Rep)
26 Jan: South Carolina primary (Dem)
29 Jan: Florida primary
5 Feb: some 20 states including California, New York, New Jersey
Mr Giuliani - who analysts say has yet to fully enter the fray - said he was looking forward to Florida's 29 January primary.
Mr Huckabee will take heart from his third place finish in a state where he was never expected to do well, our correspondent says.
The election battle now gathers pace, with Michigan holding its primary next Tuesday and Nevada its caucuses on 19 January.
And the next big contests are set for South Carolina, where Republicans hold their primary on 19 January with the Democrats in the state making their choice a week later on 26 January.
Analysts say South Carolina's large bloc of black Democratic voters is likely to go for Mr Obama, who aims to become the first black US president.