The federal Liberal party said Gray passed away peacefully at an Ottawa hospital.
"Beloved by all, Herb devoted a lifetime to his party and his country, in both good times and bad," Liberal leader Justin Trudeau said in a statement.
“He has left behind an immense legacy unmatched by most in Canadian history."
Prime Minister Stephen Harper extended his condolences to Gray's family as news of his death spread.
"He was an honourable parliamentarian who served his country well," Harper said on Twitter.
Gray's career in federal politics spanned nearly four decades, starting in Opposition to John Diefenbaker and sweeping to victory with Jean Chretien's third Liberal majority government in November 2000.
Chretien on Tuesday called Gray a great Canadian and a friend. He said Gray was "very competent, and very dedicated to the people of Windsor who had showed confidence in him for so long."
Added Chretien: "He had a great political career and should be an example for people who always criticize politicians. There are very good people serving Canada in that profession and the best example is Herb Gray."
Public service is a nobel cause and Gray was a noble man in that profession, said Chretien.
The man sometimes known as The Gray Fog was a master of deflection in the House of Commons, embodying the place where opposition questions disappeared in a miasma of polite, monotonal verbiage.
"I remember Herb Gray calmly swatting away our questions in QP when we were in opposition. It was a marvel," tweeted Industry Minister James Moore.
"He caught every fastball we threw with his bare hand and smiled — first to our frustration, then to our rhetorical astonishment and respect."
Constituents, however, said Gray was a down-to-earth politician who always looked beyond party lines when it came to their concerns.
The Windsor lawyer was first elected to the Commons in 1962 at the age of 31.
He would remain undefeated for 12 successive elections in his Windsor West riding. In the November 2000 election, he captured over 20,000 votes, more than twice that of his nearest competitor.
Gray became the first Jewish federal cabinet minister in Canadian history, appointed as minister without portfolio by former Prime Minister Pierre Trudeau.
He later held various cabinet portfolios including national revenue, consumer and corporate affairs and industry.
He took over as deputy prime minister in 1997 from Sheila Copps, who resigned amid a scandal over the Liberals' unfilled promise to scrap the GST. He left parliament in 2002.
Copps remembered Gray on Monday as a friend and "a great Canadian."
Another former Liberal MP, John Nunziata, said he was "honoured to serve with Herb Gray — a true gentleman with an amazing wit and sense of humour."
Former federal Liberal leader Bob Rae added that Gray was a man who "served Canada with such distinction and care."
Gray, known for conservative suits and cautious answers, served as Chretien's point man on many issues, including the APEC controversy and the Shawinigate affair, deflecting opposition questions about a hotel loan in Chretien's constituency.
He also headed up the file on residential school abuse, working with aboriginal groups to settle outstanding claims.
A popular figure on Parliament Hill, he was regularly voted one of its sexiest MPs.
In his riding, he was affectionately known as "the godfather of politics," and a coalition of Windsor, Ont., non-profit groups named a building after him.
When he stepped in as interim Opposition leader in 1990, he was often backed by a chorus of Liberal caucus members chanting "Herb, Herb, Herb."
Passionate about politics, he was also known for his love of political satire, and regularly tuned in to CBC's Radio's Royal Canadian Air Farce and Double Exposure.
He never took himself too seriously, said Garry Fortune, a longtime assistant.
"The two of us have had to practically pull over because of our fits of laughter, especially when they do their imitations of him," he said.
Gray would often deliver one-liners during meetings that would go over other official's heads, aides said.
A classical pianist, Gray also had a love for rock 'n' roll, listening to the likes of Bruce Springsteen and Bob Seeger. He once attended a Boy George concert.
Gray had battled several health problems in recent years, including a heart condition and a bout with cancer.
He was diagnosed with cancer of the esophagus in 1996 but recovered after radiation therapy.
He also had an operation in 1999 to treat a prostate condition unrelated to the cancer.
In August 2001, Gray underwent valve replacement surgery to correct a heart condition he had known about for years.
Prior to that surgery, he gave no hints he would be retiring anytime soon. Rumours also speculated he was a contender for Governor General in 1999 or a senate seat.
Gray leaves behind wife Sharon Sholzberg-Gray, and two children, Jonathan and Elizabeth, and eight grandchildren.
Also on HuffPost