Howe was elected to the House of Representatives at the 1977 federal election, representing the northern Melbourne metropolitan electoral Division of Batman. He defeated the incumbent Horrie Garrick for Labor preselection in a hard-fought preselection contest. It was reportedly the first occasion on which an incumbent Victorian Labor MP in a safe seat was defeated for preselection. A member of the Socialist Left faction of the Labor Party, Howe was Minister for Defence Support in the government of Bob Hawke from 1983. In 1984 he became Minister for Social Security and carried out various radical reforms to Australia's welfare system. Howe appeared to face significant opposition within his electorate in 1988, when up to 60 members of the Greek Westgarth branch of the ALP defected to join the Australian Democrats. One of the defectors, tram-conductor George Gogas, contested Batman as a Democrat candidate in 1990, but polled only 12.9 per cent of the vote. After the 1990 election Howe was appointed to the post of Minister for Community Services and Health. When Paul Keating resigned from the cabinet in 1991, Howe was elected deputy leader of the Labor Party in his place, defeating Graeme Campbell in a caucus ballot by 81 votes to 18. He was subsequently appointed Deputy Prime Minister. He became Minister for Health, Housing and Community Services in the Keating government in December 1991, dropping the health part of the portfolio in 1993. In June 1995 he resigned as Deputy Prime Minister and was succeeded by Kim Beazley. He remained in the House of Representatives until the 1996 election. Howe's last months in the Deputy PM's role were marked by speculation that his successor would be, not Beazley, but Carmen Lawrence, the erstwhile Premier of Western Australia. At the time Lawrence enjoyed considerable popularity, and there were those in the ALP who hoped that with her as Deputy PM, the Keating government would benefit. This hope was dashed when Lawrence herself became the subject of a royal commission around the time Howe left the post, although she denied that the royal commission had been her reason for not seeking out the job. Kim Beazley was eventually elected as his successor.
Later life
Following Howe's departure from parliament, the ACTU commissioned him to chair their inquiry into insecure work. In this capacity he has spoken widely about the issue to the media and addressed the National Press Club. As well as being active concerning employment-related matters, Howe is a member of the Patrons Council of the Epilepsy Foundation of Victoria.