Abe, at 52 Japan's youngest postwar prime minister, said he was quitting to pave the way for ruling and opposition parties to work together to approve the extension of Tokyo's naval mission in support of the U.S.-led operation in Afghanistan.
"In the present situation, it is difficult to push ahead with effective policies that win the support and trust of the public," Abe said in a nationally televised news conference. "I have decided that we need a change in this situation."
Abe, a nationalist whose public support rating has plunged to 30 percent, also cited the ruling party's defeat in July 29 elections, in which the opposition took control of the upper house of Parliament.
Chief Cabinet Secretary Kaoru Yosano suggested Abe also had unspecified health concerns that played a role in his decision, but he refused to release any details.
Abe said he had instructed ruling party leaders to immediately search for a replacement, but he did not announce a date for his departure. His former foreign minister, Taro Aso, is considered a front-runner to replace him, though Aso said it was too soon for him to comment.
The ruling Liberal Democratic Party announced it would use a streamlined election process to choose a successor. Kyodo News agency reported the party planned an election for LDP president next Wednesday.
The party leader is guaranteed election as prime minister because of the LDP's control of the powerful lower house of Parliament.
The sudden resignation came less than a month after Abe reshuffled his Cabinet in a bid to recover public support. He had been adamant that he would not step down to take responsibility for the LDP electoral defeat.
Abe announced his departure just as the government faced a battle in Parliament over whether to extend the country's naval refueling mission in the Indian Ocean. Just days earlier, he said he would quit if he failed to win parliamentary passage of legislation extending the mission.
But on Wednesday, Abe suggested that his departure could aid bipartisan passage of the bill.
"I have pondered how Japan should continue its fight against terrorism," Abe said Wednesday. "I now believe we need change. So Japan must continue its fight against terrorism under a new prime minister."
The United States has turned up the pressure on Japan to extend the mission. U.S. Ambassador Thomas Schieffer met with Cabinet officials, including Foreign Minister Nobutaka Machimura, earlier Wednesday to make Washington's case for extension.
The plenary session of the lower house was to be delayed until at least Friday, and the opposition criticized Abe for quitting just as the session was to heat up.
"I've been a politician for nearly 40 years, but I think this is the first time that a prime minister has remained in office after the ruling party lost a majority ... and expressed his resignation right before parliamentary questioning," said Ichiro Ozawa, leader of the opposition Democratic Party of Japan.
Abe's resignation marked a rapid fall from power for a prime minister who came into office a year ago with ambitious plans to repair frayed relations with Asian neighbors, revise the 1947 pacifist Constitution, and bolster Japan's role in international diplomatic and military affairs.
The prime minister, whose grandfather was also a prime minister and whose father was a foreign minister, initially met with success in fence-mending trips to China and South Korea. He also passed laws bolstering patriotic education and upgrading the Defense Agency to a full ministry for the first time since World War II.
But a string of scandals starting late last year quickly eroded his support. Four Cabinet minister were forced to resign over the past nine months, and one - his first agriculture minister - committed suicide over a money scandal.
Abe was also hurt by a scandal over the loss of some 50 million pension claims. He apparently ignored early warnings of the looming scandal, and then defended the government when news of the losses broke.
Support for the political blue blood was also damaged by his concentration on ideological issues - such as patriotism and constitutional reform - at a time when many Japanese are concerned over the widening gap between rich and poor and other bread-and-butter worries.
In such a weakened state, Abe may have feared he wouldn't have the clout to win passage of the Afghan mission, said Eiken Itagaki, a political analyst and writer.
"He has run out of political capital," Itagaki said. "So he bolted, in the hope that a more experienced successor can save the mission, and sort out the mess."
A Chinese Foreign Ministry statement praised Abe for presiding over a "clear improvement" in relations that nose-dived under Abe's predecessor, Junichiro Koizumi, and called for continued closer ties. SouthKorea was similarly positive.
The U.S. Embassy in Tokyo said in a statement that the American government would "continue to work closely" with Japan to further common interests.
Though Aso is considered a front-runner to succeed Abe, it is not clear whether he has the political and public support to stop the LDP's slide in popularity.
Other possible candidates listed by local media include Yosano and former Finance Minister Sadakazu Tanigaki.