Born in 1965 in Buckingham, Quebec, Lemieux played two years of junior hockey with the Verdun Junior Canadiens and the Trois-Rivieres Draveurs and was drafted by the Montreal Canadiens in 1983, the team's fourth pick and 26th overall. At only eight games, his stay with the Canadiens wasn't a long one and he returned to play in the minors for the next several years, making the occasional trip with the Canadiens. He began to establish his reputation as a playoff performer in 1985, landing the Guy Lafleur Award as the most valuable player in the QMJHL playoffs. The next season, after playing with Montreal for 10 games in the regular season, Lemieux helped the Canadiens land the Stanley Cup with his 10 playoff goals, including four game-winning goals, the equivalent of a series win.
He played his first full season with the Canadiens in 1986-87, scoring 27 goals and 53 points. For his clutch play, he was named to the Team Canada squad for the 1987 Canada Cup and to the NHL team in the Rendez-Vous 87' matchup with the Soviet Union that replaced the All-Star Game.
Lemieux stayed with the Canadiens, scoring as many as 31 goals in a season (1987-88), until he was traded at the beginning of the 1990-91 season to the New Jersey Devils for Sylvain Turgeon. Lemieux had a breakout season offensively with New Jersey, scoring 41 goals in 1991-92 and the following season recorded a career-high 81 points. He saved his best for the playoffs, however. He had 18 points in 20 playoff games in 1994 when the Devils lost a close seven-game series to the eventual champion New York Rangers. Lemieux was the leading goal scorer in the 1995 playoffs with 13, including three more game-winning goals. After the Devils won the Stanley Cup, Lemieux was awarded the Conn Smythe Trophy as the most valuable player in the playoffs.
Lemieux was dealt to the Colorado Avalanche prior to the 1995-96 season. Upon his arrival in Denver, Lemieux became the fourth player to win a Stanley Cup with three different teams, joining Al Arbour, Larry Hillman and Gord Pettinger (Mike Keane has since become the fifth with his Stanley Cup victory with the Dallas Stars in 1999) when Quebec moved to Colorado and marched to the championship. It was only the fifth time a player had won the Cup two consecutive years with different teams.
Lemieux was selected to the Team Canada roster for the World Cup in 1996 and, with his chippy demeanor still intact, he picked up 19 penalty minutes in the eight games as Canada finished second. The next season, Lemieux starred again in the Stanley Cup playoffs, leading the league with 13 goals before Colorado was defeated by the Detroit Red Wings. Early in the 1999-00 season, Lemieux returned once again to the Devils, as New Jersey looked forward to the playoffs. His 19 game-winning goals in the playoffs puts him in second place on the NHL's all-time list behind Wayne Gretzky, who had 24, and one ahead of Maurice Richard.
In the summer of 2000, Lemieux signed as a free agent with the Phoenix Coyotes and spent parts of three seasons with the team before being dealt to the Dallas Stars midway through the 2002-03 season. Lemieux would end his NHL playing career with Dallas following the end of the 2002-03 season, however would suit up for EV Zug in Switzerland briefly in 2003.
Over five years later, Lemieux returned to the ice once again. After starting his 2008-09 season with the China Sharks, Lemieux played in 23 games with the American Hockey League's Worcester Sharks, recording 11 points. The veteran winger was recalled by the Sharks' parent club which completed the remarkable comeback for the 43-year-old Buckingham, Quebec native.