Kaieda was born and grew up in Suginami, Tokyo. He is named after the Great Wall of China (万里の長城, Banri no Chōjō) as his father was a newspaper correspondent who covered China and Taiwan. He graduated from Keio University where he studied political science, English, German and Chinese. He became known as a television personality in the late 1980s and early 1990s, both in comical roles and as a serious newscaster (hosting the Saturday evening news program on TV Tokyo from 1989 to 1991).
Kaieda worked as an economic analyst and secretary to a member of the House of Councillors before winning election to the House of Representatives in the 1993 general election. He was originally a member of the Japan New Party, then formed a short-lived party following the JNP's collapse, and was one of the founding members of the Democratic Party of Japan in 1996. He retained a seat in the Tokyo proportional representation block in the 1996 general election, losing his Tokyo 1st district seat to Kaoru Yosano of the LDP. He regained his district seat in the 2000 election and 2003 election, but was forced out of the House of Representatives in the 2005 election, both losing his district seat to Yosano and failing to win a PR seat.
Kaieda re-won the Tokyo 1st district seat in the 2009 general election, following which the DPJ was able to form a government.
Kaieda was tapped to serve as Minister of State for Economic and Fiscal Policy from September 2010, in which role he encouraged the Bank of Japan to purchase foreign currency assets in order to stop a sharp appreciation in the value of the Japanese yen.
In January 2011, he was appointed to head the Ministry of Economy, Trade and Industry by Prime Minister Naoto Kan. The Fukushima disaster in March 2011 made evident numerous missteps within the ministry, and Kaieda stepped down as economy minister in August in order to take responsibility. He had been under intense pressure to resign from the Liberal Democratic Party, and was brought to tears on the Diet floor following 20 minutes of berating from LDP legislator Ryosei Akazawa days earlier.
After Kan resigned in August 2011, Kaieda competed to replace him, supported by former DPJ leader Ichirō Ozawa, then under suspension from the party after being indicted for alleged violation of the Political Funds Act. Kaieda lost a runoff vote against Yoshihiko Noda, achieving 177 votes to Noda's 215.
In the 2012 election, the DPJ under Noda suffered a major defeat. Kaieda lost his seat representing the Tokyo 1st district to LDP newcomer Miki Yamada but retained a Diet seat through proportional representation.
Noda resigned as president of the DPJ to accept responsibility for its defeat in the 2012 election. The resulting DPJ presidential election was held on 25 December 2012, which was contested by Kaieda and Sumio Mabuchi. It was eventually won by Kaieda with 90 votes to Mabuchi's 54 votes. It was suggested that his rise to the leadership could lead to cooperation with Ozawa, who had left the DPJ during 2012 due to Noda's pushing through of a consumption tax increase.
After the 2013 House of Councillors election, in which the DPJ suffered another defeat, Kaieda reportedly approached Naoto Kan and asked him to leave the party.
Despite the DPJ recovering a few seats in the 2014 snap election, Kaieda lost his district seat. He resigned as leader of the DPJ and Katsuya Okada succeeded him as president of the DPJ.
According to a Gay Japan News 2009 election questionnaire, he supported legalization of gay marriage in Japan and indicated a desire to put support for gay rights into the Democratic Party of Japan's party platform.