The Grizzlies also received a 2013 second-round pick from Toronto as part of the deal.
The Dallas Mavericks, sources said, were also interested in acquiring Calderon but were not prepared to surrender swingman Vince Carter, whom Memphis coveted to help fill the void created by Gay's departure.
Memphis general manager Chris Wallace thanked both Gay and Haddadi for their time with the Grizzlies.
"We are excited to add three players who bring with them a tremendous amount of value to our team and have achieved incredible success on the pro, college and Olympic levels," Wallace said in a statement Wednesday night. "In these players, we welcome NBA Champion and Olympic gold medalist Tayshaun Prince, as well as up-and-coming athletic forwards Ed Davis, who won an NCAA title at North Carolina, and Austin Daye."
The moves surprised many around the league, including Calderon.
"It's been my home for eight years," Calderon said in Atlanta, shortly before leaving the arena. "I've done everything possible for this team. It's tough. The fans have been with me since Day 1. It's tough."
Prince and Daye have both spent their entire careers with Detroit, and Prince was the last link to the proud championship team of 2003-04.
"Trading a player like Tayshaun Prince, who has meant so much to our organization and contributed to our championship success, is never easy," Pistons president Joe Dumars said in a statement. "We want to thank Tayshaun for his professionalism and contributions over the last 10 years. We also appreciate everything that Austin Daye has done for our team both on and off the court over the past three-plus years."
Gay, averaging 17.2 points and 5.9 rebounds, signed a five-year, $82 million maximum contract in July 2010 with Memphis. The 6-foot-8 small forward is due $16.5 million this season with $37 million more over the next two years. That's a big number for new owner Robert Pera, who took over the franchise last November and has quickly started addressing the team's salary situation.
Just more than a week ago, the Grizzlies sent valuable reserve Marreese Speights and two other players to Cleveland in a move that cleared $6.4 million in salary and avoided a $4 million luxury tax hit this season. Team officials said that move put the Grizzlies in position not to have to make a move this season.
Memphis coach Lionel Hollins had been lobbying to keep his five starters together the rest of this season, but he apparently lost that fight. It's a significant move for a team that was fourth in the Western Conference and three games behind the third-place Clippers.
"Wow," Grizzlies point guard Mike Conley tweeted.
Trading away Gay also eases a luxury tax hit due next season, while concentrating the team around center Marc Gasol and All-Star forward Zach Randolph. The Grizzlies had their best playoff run in 2011 when they knocked off then-No. 1 seed San Antonio before losing to Oklahoma City in seven games in the Western semifinals -- all with Gay on the bench after needing season-ending shoulder surgery.
"Wow that was 1 crazy trade today," Oklahoma City center Kendrick Perkins tweeted. "Are you serious Rudy Gay is right there under KD, Lebron, Kobe, and Melo. (hashtag)badtrade."
They do run the risk of upsetting the chemistry on a tight-knit group, even if there were some questions of how Gay's scoring fit in with the ball-dominant frontcourt of Gasol and Randolph.
But there may be more deals like this one coming in the new NBA economy.
The collective bargaining agreement negotiated after last year's lockout makes the penalties for exceeding the salary cap far more punitive, and the system begins in earnest next season. Playing in a smaller market, the Grizzlies don't have the extra revenue from lavish television contracts like teams in Los Angeles or New York, which makes it that much more difficult to go over the cap.
But even teams such as the Lakers and Bulls likely will have to be more responsible with their spending under the new deal, where repeat offenders are taxed at rates that multiply with each consecutive year they go over the cap.
The first domino fell before the season, when Oklahoma City sent James Harden to Houston instead of signing him to a big-money extension. More are sure to follow.
All told, the Grizzlies shaved nearly $40 million over the next three years after the two trades.
They'll get a hard-nosed defender in return in Prince, the 32-year-old forward who was drafted by the Pistons in the first round in 2002. He is averaging 11.7 points and 4.6 rebounds per game this season. Bringing in Calderon gives Detroit a veteran mentor for young point guard Brandon Knight.
"We are pleased to welcome Jose Calderon, knowing that he fits our mold as a high character individual who is a great competitor," Dumars said. "Jose is a great facilitator at the guard position and a player that we feel gives us tremendous flexibility on the court when added to the core of guards we have on the roster."
Calderon joined the Raptors from Spain in 2005 and has been a fan favorite and trusted veteran on the team. He is averaging 11.1 points and 7.4 assists this season for the Raptors (16-29), who are desperately trying to scratch their way into the playoff picture. Toronto was in 11th place before the games were played Wednesday, 5½ games behind Boston for the eight seed.
Calderon and Davis had both been starting for the Raptors, but they do have Kyle Lowry waiting in the wings at point guard and likely see Gay's scoring punch as the key to vaulting back into the discussion in a mediocre conference.
But getting a player with Gay's natural scoring talent, even at the expense of parting with a valued player like Calderon, proved too enticing to pass up.
"Hopefully this team is back to the playoffs as soon as possible," Calderon said.
Information from ESPN.com's Marc Stein and The Associated Press was used in this report.