US Defence Secretary Donald Rumsfeld is to stand down, after anger over the war in Iraq led to bruising losses for Republicans in mid-term elections.
President George W Bush said that he and Mr Rumsfeld had agreed that a "fresh perspective" was needed in Iraq.
Former CIA Director Robert Gates has been nominated to replace Mr Rumsfeld.
The Democrats won control of the House of Representatives in the polls, and AP news agency says they are also set to take the Senate.
"It's been quite a time," said Mr Rumsfeld in a short departing speech, delivered alongside President Bush, two hours after the president had announced that he would be replaced.
As a key architect of the war in Iraq, Mr Rumsfeld had faced growing calls to quit as violence has continued to spiral, three years after the US-led invasion.
"I have benefited greatly from criticism, and at no time have I suffered a lack thereof, " Mr Rumsfeld said, quoting Winston Churchill.
He described the Iraq conflict as a "little understood, unfamiliar war" and said he was confident of ultimate success there.
But BBC News website world affairs correspondent Paul Reynolds says his resignation is a sign and an admission that the US policy in Iraq has not worked, so far.
Mr Bush described Mr Rumsfeld as a "patriot who served this country with honour and distinction", as well as "a trusted adviser and a friend".
"America is safer and the world is more secure" as a result of Mr Rumsfeld's leadership, he said.
However, Democrats welcomed Mr Rumsfeld's resignation.
"Secretary Rumsfeld's war plans in Iraq have failed. The country is on a dangerous course, and the administration has finally recognised the need for drastic, immediate change," said Senator John Rockefeller, senior Democrat on the Senate Intelligence Committee.
Meanwhile the editor-in-chief of the Military Times, a newspaper group which includes four papers which at the weekend called for Mr Rumsfeld's resignation, said Mr Gates' appointment was "promising".
"I think that the change at the top also is a signal to allies that we are going to be perhaps a little more open-minded than we have been in the past," said Tobias Naegele.
After the 9/11 attacks on America, Mr Rumsfeld led the planning and execution of the US invasion of Afghanistan in 2001 and the military operation in Iraq two years after that.
As we know, there are known knowns, there are things we know we know - we also know there are known unknowns ...
Popular frustration over the war in Iraq has been a key factor during the current election campaign, and correspondents say Mr Rumsfeld had been looking increasingly beleaguered because of its apparent failures.
Mr Bush announced that Mr Rumsfeld was standing down minutes after the news came that the Democrats had won the Senate race in Montana, one of the two remaining seats needed to wrest control of the upper chamber of Congress from the Republicans.
The US president described as "thumping" the Republicans' setback in the elections, in which the Democrats gained control of the House of Representatives for the first time in 12 years.
The Democrats celebrated major gains in the House and Senate
Mr Gates, 63, will need to be confirmed by the Senate as the new defence secretary. Mr Rumsfeld will continue in his post until then.
Mr Gates served as CIA director for just over a year in the early 1990s, during the presidency of Mr Bush's father.
He is a member of the bipartisan Iraq Study Group, which is tasked with recommending ways of tackling the problems the US faces in Iraq.
Mr Gates said he believed the outcome of the current conflicts in Afghanistan and Iraq would "shape our world for decades to come" and pledged to serve "with all my heart".
The BBC's John Simpson in Baghdad says there will be few tears shed by Iraqis for Mr Rumsfeld, who is identified as the architect of the brutal and dangerous conditions of daily life in the country.
He was subjected to unprecedented criticism following revelations of abuse of Iraqi prisoners by US troops at Abu Ghraib jail, and he twice offered to resign over the issue.
Resentment has grown further against the US presence in Iraq as violence has spiralled.
Despite a bitter, fiercely fought election campaign, Mr Bush said he was looking forward to working with Democrats.
"If you hold grudges in this line of work, you never get anything done," he said.
He said he would seek to find "common ground" with House Democratic leader Nancy Pelosi, who is set to become the first female speaker in the lower chamber.
Earlier she pledged that the Democrats would work with "civility" and "partnership, not partisanship" in their newly empowered position.