Tony Blair says he will "focus relentlessly" on the public's priorities after securing a historic third term in government.
Mr Blair acknowledged that the Iraq war had been "deeply divisive" but said he believed people wanted to move on.
He pledged to tackle immigration issues and re-establish respect in classrooms, town centres and on Britain's streets.
Labour is expected to see its majority cut from 167 in 2001 to 66. The Tories have 197 seats and the Lib Dems 62.
The Tories gained 31 seats from 2001, while the Lib Dems won 10 more seats.
As the last results arrived in Northern Ireland, Ulster Unionist Leader David Trimble has lost his Upper Bann seat.
The Nobel peace prize winner's seat was among two gains for Ian Paisley's Democratic Unionists Party.
Conservative leader Michael Howard has announced he will be standing down from the job before the next election.
He will stay as leader until the party's rules on selecting a successor have been changed.
Mr Howard said he would be too old, at 67 or 68, to lead the party at the next election, and would step aside "sooner rather than later".
However, he said the Tories' result had "begun the process of rebuilding our party, of building a broad and outward-looking party that reflects Britain in the 21st Century".
Mr Blair is the only Labour leader to have won three elections in a row, but his margin of victory is less than half what it was in the Labour landslides of 1997 and 2001, and he has the lowest share of the vote for a ruling party in modern times.
On Friday he was thought to be adding the finishing touches to a Cabinet reshuffle, having been given formal consent by the Queen to form a new government.
Mr Blair, who celebrates his 52nd birthday on Friday, said it was "a tremendous honour and privilege" to be elected for a third term.
Watched by his wife Cherie and four children, he said: "The great thing about an election is that you get out and talk to people for week upon week and I have listened and I have learned.
"I think I have a very clear idea of what the British people now expect from this government for a third term."
In a swipe at the Tory campaign, Mr Blair said he had learned that Britons were "tolerant and decent" people who had not wanted immigration turned into a "divisive issue".
"But they do believe there are real problems in our immigration and asylum system and they expect us to sort them out and we will do so," he said.
People had also signalled their dislike of the lack of respect in the classroom, on streets and in town centres on Friday and Saturday nights, he said.
"I want to make this a particular priority for this government - how we bring back a proper sense of respect in our schools, in our communities, in our towns, in our villages."
Mr Blair said there would be a "radical programme" of legislation to deal with the priorities of education, health and law and order.
The government had a "very, very big agenda for a third term", with the "experience as well as the commitment to see it through".
Provisional figures suggest 22% of those eligible to vote backed Labour - the lowest figure they have received at any post-war election apart from 1983 when the figure was 20.6%.
Turnout is up about 2% thanks to big increases in marginal seats.
Tories unseat Labour minister Stephen Twigg
George Galloway wins in Bethnal Green
Independent Richard Taylor wins again in Wyre Forest
Peter Law, who quit Labour in protest at all-women short-lists, overturns a 20,000 Labour majority to win Blaenau Gwent
The Conservatives did best in the South East, where they had a 2.3% increase in the share of the vote, and London, where they regained Putney and Wimbledon and unseated schools minister Stephen Twigg, who famously snatched Enfield Southgate from Michael Portillo in 1997.
The Tories also gained Shipley from Labour - unseating junior minister Christopher Leslie - Welwyn Hatfield from health minister Melanie Johnson, and Newbury from the Lib Dems.
The Lib Dems, who look set to end up with an estimated 60 seats, held on to Cheadle, which had been the Conservatives' top target, and unseated Labour ex-minister Barbara Roche on a 14% swing.
But they failed in their "decapitation" strategy to unseat ex-Tory chairman Theresa May and shadow home secretary David Davis and Oliver Letwin, who all retained their seats with increased majorities.
Only one member of the Tories' top team - education spokesman Tim Collins - was ousted.
Lib Dem leader Charles Kennedy said voters had ushered in a new era of three-party politics as he was returned as an MP by an overwhelming majority.
"I think it is going to be a very different House of Commons from the one we have had over the past eight years, and I think that is going to be very healthy, whatever people's political views," he added.
In one of the biggest upsets of the night, George Galloway, of the anti-war Respect party, narrowly beat Labour's Oona King, who voted for the Iraq war, in Bethnal Green, one of the most bitter contests in the 2005 election.
Mr Galloway, who based his campaign on opposition to the Iraq war, said: "This is for Iraq."
In a further sign of the impact of the Iraq war, there was a significant swing from Labour to Lib Dem in most of the 40 seats with a large Muslim population.
Mr Galloway's success means that there are more small party and Independent MPs than in any parliament since 1945, with wins for Richard Taylor in Wyre Forest and for Peter Law, who quit Labour in protest at all-women short-lists.
Turnout up slightly on 2001
Anti-war candidate Reg Keys polls 10% in Sedgefield
Alan Milburn quits frontline politics
Lib Dems win Manchester Withington on 17% swing from Labour
Lib Dems fail to unseat top Tories
BNP gains 5% of vote in seats where they stood
Robert Kilroy-Silk narrowly misses losing his deposit
BNP leader Nick Griffin took 9% of the vote in Keighley, where Labour's Anne Cryer was returned as the town's MP.
The Greens gained 22% of the vote in Brighton Pavilion, beating the Lib Dems into fourth place, but their vote was up just 0.4% nationally. UKIP's national share was up 0.8%.
In Northern Ireland, where results in 18 Westminster constituencies are still coming through, Sinn Fein President Gerry Adams held his West Belfast seat increasing his share of the vote by 4%.