Elsewhere across England, Labour lost control of 15 local councils with the Tories gaining ground. But there was a surprise as the Conservatives lost to the Liberal Democrats in the Romsey by-election.

First preference votes

Ken Livingstone (Independent): 38.11% Steve Norris (Conservative): 26.5% Frank Dobson (Labour): 12.78% Susan Kramer (Liberal Democrat): 11.6% Ram Gidoomal (Christian Peoples' Alliance): 2.45% Darren Johnson (Green): 2.22% Michael Newland (British National Party): 1.96% Damian Hockney (UK Independence Party): 0.95% Geoffrey Ben-Nathan (Pro-motorists): 0.58% Ashwinkumar Tanna (Independent): 0.53% Dr Geoffrey Clements (Natural Law Party): 0.32%

An emotional Mr Livingstone, who was expelled from the Labour Party after choosing to run as an independent, praised his opponents and said he would invite them to work in his new administration.

He said: "Amongst the candidates there has been dignity and genuine respect. I want to pay tribute to the way they have conducted themselves.

"In particular I want to say a word to my old colleague and friend Frank Dobson, who has borne a terrible brunt of odium which was not his but should have been rightly reserved for people who work behind the scenes."

Steve Norris came back strongly but couldn't catch Mr Livingstone

Mr Dobson said he accepted his share of Labour's failure, but said he hoped he had not let too many people down.

He said he had enjoyed the campaign and did not regret his decision to stand.

Prime Minister Tony Blair said he would be speaking to Mr Livingstone but added that his views about the left-wing MP had not changed.

'Difficult campaign'

He said: "It is important that we do what we can as a government to make sure that this works for London and works for Londoners. We accept our responsibility in that regard."

Frank Dobson: No regrets over standing in mayoral contest

But Mr Blair made it clear Mr Livingstone would not be allowed to return to Labour after standing against an official party candidate.

And he praised Mr Dobson's "decency during an extremely difficult campaign".

Of first preferences in the mayoral vote, Mr Livingstone polled 38.11% to Mr Norris' 26.5%, with Mr Dobson on just 12.78% and Liberal Democrat Susan Kramer behind him on 11.6%.

Both Mr Dobson and Ms Kramer were eliminated from the contest after the first round, with their second preference votes then redistributed to Mr Livingstone and Mr Norris.

In the elections for the 25 Greater London Assembly constituency seats, the Tories and Labour both won nine and the Liberal Democrats won four, while the Green Party picked up three seats.

Low turnout

Mr Dobson's humiliation in the mayoral poll was underlined as he came fourth in the mayoral contest in Barnet and Camden - the seat which includes his parliamentary constituency.

I think the overwhelming sentiment - rather than logic - in this election has been poking Blair in the eye with a stick

Steve Norris

Despite a turnout of just 33.6%, with 1.7m people voting, Mr Livingstone's triumph was announced just after 1215 BST on Friday - more than 12 hours after polls closed - following problems with counting equipment.

Mr Livingstone said he would fight for the interests of Londoners as mayor, demanding more money from the government and telling ministers they were wrong over plans to partially privatise the London underground.

Greater London Assembly seats

Conservatives: 9 Labour: 9 Lib Dems: 4 Green Party: 3

And he said he would now try to "draw a line in the sand in what has been a very unpleasant and divisive campaign, to try and bring all the parties into a broad coalition to try to do our best for London".

If the Archangel Gabriel had stood with the name Winston Churchill, Ken would still have won

Lord Archer

Ministers moved quickly to extend an olive branch to Mr Livingstone, with Education Secretary David Blunkett urging him to "work together" with the government.

Mr Norris said London had given Mr Livingstone "merely a conditional mandate", adding: "If this trend continues he will be on probation as London's mayor."

Lord Archer, who was forced to stand down as Tory mayoral candidate amid a scandal, said no candidate could have beaten Mr Livingstone after the controversy over Labour's selection process.