Rumsfeld, who had served as Mr. Bush's Secretary of Defense since 2001 and held the same position between 1975 and 1977 under President Ford, had been heavily criticized for an unpopular war in Iraq, which has claimed more than 2,800 lives since its inception in 2003.
"Secretary Rumsfeld and I agreed that the timing is right for new leadership in the Pentagon," President Bush said at a press conference from the White House.
Mr. Bush said Rumsfeld had been "a superb leader in a time of change," providing a "fresh perspective in a critical period in a time of war," but that Rumsfeld himself admitted Iraq policy is "not working well enough, fast enough."
The Associated Press reported that exit polls from the previous night's election showed voters' dissatisfaction with the war as a significant contributor to dramatic victory for Democrats in the House of Representatives.
Last week, the president had campaigned to save the Republican majority, declaring that Rumsfeld would remain at the Pentagon through the end of his term.
Earlier on Wednesday, a spokesman for Rumsfeld said that he had given no indication that he would step down.
With a change in power underway in the Pentagon, Mr. Bush sent specific messages to those involved in the war in Iraq. He told the terrorists "do not be joyful", Iraqis "do not be fearful," and U.S. troops "don't be doubtful."
The president insisted that U.S. troops would not leave before their mission was complete in Iraq. "We cannot accept defeat," he said.
Mr. Bush said he would nominate current Texas A&M University president Robert Gates, "a steady, solid leader," to succeed Rumsfeld.
Gates first joined the CIA in 1966 and served in the intelligence community for more than a quarter century under six presidents, including a two-year stint as CIA director that began under President George H. W. Bush.
Gates' nomination must be confirmed by the Senate.
Mr. Bush stressed that Gates, a member of the ongoing presidential commission headed by former Secretary of State James Baker and former Rep. Lee Hamilton that is charting a new course in Iraq, would bring "more than 25 years of national security experience" to the Pentagon.
The president said he would be meeting with Hamilton and Baker early next week to discuss their possible recommendations for a new policy towards Iraq.