Gagnon started his Olympic career in 1994, when he had already won the 1993 World Championships. He won a bronze in the 1000 m event. Four years later, in Nagano, Japan, Gagnon won a gold medal with the Canadian relay team. The 2002 Salt Lake City Games proved to be Gagnon's best Olympics, with a total of three medals. A bronze in the inaugural 1500 m event, and two golds; in the 500 m and again as a part of the relay team. Even his disqualification in the 1000 m was memorable, as it was the first of an improbable series of events that led to Australian Steven Bradbury winning arguably the most unlikely gold medal in Olympic history.
Winning a total of five medals in three consecutive Winter Games made him the most decorated Canadian athlete in Winter Olympic history until 2006. He has now been overtaken by long track speed skater Cindy Klassen and long track speed skater/road cyclist Clara Hughes, who each have a total of 6 medals. Tied with track and field athlete Phil Edwards and fellow short track speed skater François-Louis Tremblay, he is one of the five most decorated Canadian athletes in all Olympic Games.
Gagnon won his World Championships in 1993, 1994, 1996 and 1998. He is the first man to have become a four-time Overall World Champion. In addition, he finished 2nd twice, and third once.