The prime minister is trying to regain momentum after one of the worst local election results in Labour's history.
Mr Clarke will be replaced by Defence Secretary John Reid. Margaret Beckett is the new foreign secretary, with Jack Straw becoming Commons leader.
John Prescott will stay as deputy prime minister but lose his department. Trade Secretary Alan Johnson gets education.
Labour came third in the overall share of the vote in local elections in England, losing control of 18 local authorities. The Tories were the biggest winners, gaining 316 extra councillors and 40% of the vote.
CABINET RESHUFFLE Foreign Secretary - Margaret Beckett Home Secretary - John Reid Education Secretary - Alan Johnson Commons leader - Jack Straw Transport Secretary - Douglas Alexander Environment Secretary - David Miliband Local Government - Ruth Kelly Defence Secretary - Des Browne Trade Secretary - Alistair Darling Party Chairman - Hazel Blears Chief Whip - Jacqui Smith Chancellor of Duchy of Lancaster - Hilary Armstrong Chief Secretary to the Treasury - Stephen Timms
Clarke defiant Analysis: Blair wields the axe Reshuffle: At-a-glance
The results - which saw Labour lose 319 councillors - prompted Mr Blair to push ahead with a reshuffle originally planned for Monday.
The reshuffle comes amid reports a letter is circulating among Labour MPs calling for Mr Blair to name a date for his handover of power to Chancellor Gordon Brown.
The PM said he was "sorry" to lose Mr Clarke, who has been under intense pressure over the deportation of foreign prisoners - one of a series of scandals to have rocked the government in recent weeks.
But he added: "I felt that it was very difficult, given the level of genuine public concern, for Charles to continue in this post."
Mr Clarke, who had wanted to stay in his job to sort the deportation debacle out, refused the offer of other Cabinet posts, opting instead to return to the backbenches.
He said he did not agree with the prime minister's judgement in sacking him but insisted he would remain loyal to the government.
Prescott's role reduced
Mr Prescott has also been accused of damaging his party after revelations about an affair with his diary secretary.
He will remain as deputy prime minister but will be stripped of many responsibilities. He will also continue as deputy leader of the Labour Party.
ELECTION SCOREBOARD Councillors Councils PARTY +/- TOT +/- TOT CON 316 1830 11 68 LAB -319 1439 -17 30 LD 2 909 1 13 OTH -2 240 0 0 NOC - - 6 66 After 176 of 176 councils
NOC = No control
Full results
Ruth Kelly will take over many of his government roles, in a new department of communities and local government. She also takes on the title of minister for women from Tessa Jowell who remains as culture secretary.
Downing Street is insisting Mr Prescott has not been demoted and confirmed he would keep his grace and favour accommodation in recognition, it said, of his heavy workload as deputy prime minister and chairing Cabinet committees.
But Shadow Chancellor George Osborne attacked Mr Prescott as a waste of public money.
"John Prescott loses his department but keeps the trappings of office - including the car, the salary, and the two grace and favour homes," said Mr Osborne.
"Add it all up, and the taxpayer is going to be paying more than a quarter of a million pounds a year. If you're looking for ways to cut waste in government, you can start with John Prescott."
Tory 'alternative'
Meanwhile, in other moves, Trade Secretary Alan Johnson, a former postman and trade union leader, will replace Ms Kelly as education secretary and Commons leader Geoff Hoon will become Europe minister. Patricia Hewitt stays at health.
Giving his reaction to the moves, Conservative leader David Cameron said: "It will take far more than a reshuffle. What we need in this country is a replacement."
He said the Conservatives were "showing there is a broad-based alternative that is building while the government is collapsing".
In other developments, Douglas Alexander will take over as transport secretary and minister for Scotland from Alistair Darling, who goes to trade and industry.
Home Office minister Hazel Blears becomes Labour Party chairman and Des Browne is promoted from chief secretary of the Treasury to defence secretary.
Chief whip Hilary Armstrong becomes chancellor of the Duchy of Lancaster, with a new role as social exclusion minister. David Miliband becomes environment secretary.
One of the few senior ministers to remain in his post is Gordon Brown, who called the local election results a "warning shot", and said he would be speaking to Mr Blair over the weekend to plot the way ahead.
Meanwhile the chancellor's former key adviser Ed Balls, who became a Labour MP at the last general election, has secured his first government job being appointed financial secretary to the Treasury.
The reshuffle followed Thursday's local elections, which saw the Conservatives take control of 11 local authorities, although they failed to make hoped-for progress in Northern cities such as Manchester and Liverpool.
The Liberal Democrats failed to make predicted advances, gaining less than 20 councillors, but Sir Menzies Campbell insisted it was not a test of his leadership.
He said Mr Blair should have sacked Mr Clarke "before now", saying the prime minister was "trying to shuffle a pretty battered pack of cards".
'Deckchairs on Titanic'
Some Labour backbenchers believe Mr Blair must go further than just overhauling his top team.
HAVE YOUR SAY It's the Night of the Long Knives - only in broad daylight
Kevin Potter, Suffolk, UK
Send us your comments
Former Health Secretary Frank Dobson said a reshuffle would be like "rearranging the deckchairs on the Titanic".
"Quite frankly we need the party under new management," said Mr Dobson.
If Thursday's polls had been held nationwide, the Tories would have gained 40% of the vote, Lib Dems 27% and Labour 26%. Turnout is estimated at 36% - down three points from 2004.
Among the smaller parties, the Greens gained 20 more councillors and The British National Party more than doubled its previous total of 20 councillors, including winning 11 seats from Labour in Barking.
George Galloway's Respect gained 11 councillors in Tower Hamlets - but failed to stop Labour keeping overall control.
The United Kingdom Home Secretary Charles Clarke has lost his position in a Cabinet reshuffle by Tony Blair, on the morning after the Labour Party suffered losses in local elections across England. The news follows two weeks of headlines caused by the release of over 1000 foreign prisoners mistakenly released from prison at the end of their sentence rather than being deported.

Current Defence Secretary John Reid will replace Clarke as the new Home Secretary, and Jack Straw will become Commons leader.