Labour is facing an historic defeat in European elections which have seen the BNP gain its first seats in Brussels.
Gordon Brown's party looks set to finish behind UKIP, with less than 20% of the popular vote - increasing pressure on the PM to stand down.
Labour's biggest defeat was in Wales, where it lost 12% of its vote on 2004.
BNP leader Nick Griffin won a seat in the North West and Andrew Brons won one in Yorkshire and Humberside, claiming a blow against EU "dictatorship".
But the result was condemned across the political spectrum, with the Tories and Labour both branding it a "sad day" for British politics.
The Conservatives are on course to repeat their European election victory of 2004 with 27% of the vote. The Lib Dems are neck-and-neck with Labour on 16%.
Labour was beaten into fifth place behind the Greens in two English regions - the South-East and South-West, where its vote halved on 2004 and was the only region so far not to elect a Labour MEP.
Hannan's poetic call for Brown to go
UKIP is on course to come second, with 13 MEPs, one more than in 2004.
UKIP Leader Nigel Farage said his party's performance was a "hell of an achievement," as its chances were written off by some pundits ahead of the campaign.
He said it sent a clear signal to Gordon Brown: "If we have beaten him, he has got to go."
Conservative MEP Daniel Hannan, whose YouTube attack on Gordon Brown became a worldwide hit - said Labour was enduring its worst poll performance since it became a national party in the 1920s.
"I am not sure people have a complete grasp of the magnitude of what is happening," he told BBC News.
Pressure on Brown
And he repeated Conservative calls for a general election, saying: "The only reason now for keeping Gordon Brown is fear of the electorate".
Labour group leader Glennis Willmott blamed Labour's disastrous showing on the Westminster expenses scandal, which she said was the "only thing people were talking about" on the doorstep".
But she called on the party to rally behind Mr Brown.
The Greens increased their share of the vote to 9% but leader Caroline Lucas blamed the electoral system for her party's failure to gain more than its current two MEPs.
BNP wins European parliament seat
"Even though our share of the vote has gone up by about 50% our representation hasn't," she said.
The results are likely to pile further pressure on Gordon Brown, who faces a crunch meeting of Labour MPs on Monday, which may decide his future.
Former Lord Chancellor Lord Falconer repeated his call for a new leader to re-unify the party.
"I think unity will only come with a leader that the mainstream votes for," he said.
In Scotland, the Nationalists were outpolling Labour by a clear margin in the early results.
The SNP looked certain to finish the night ahead of Labour in the popular vote - achieving the goal which SNP leader Alex Salmond had set his party.
Overall, shadow foreign secretary William Hague expressed confidence that the Tories would top the national poll with around the same share of the vote as in 2004.
"We are advancing in all parts of the country," he said.
In the English local elections held on Thursday the Conservatives got a projected 38% of the vote, the Lib Dems 28% and Labour 23%.
In the 2004 European elections the Conservatives won 26.7% of votes, Labour 22.6%, UKIP 16.1%, the Lib Dems 14.9%, the Greens 6.3% and the BNP 4.9%.