In 1994, the final year of his career, he also gained fame outside the speed skating world by winning three gold medals at the 1994 Winter Olympics in his native Norway, winning all races in new World Records, two of which would remain unbeaten until the clap skate era.
Born in Drammen, Koss became a national junior champion in 1987, but he could not compete with the top skaters in the 1986 and 1987 World Junior Championships. In 1988, he debuted with the seniors at the World Championships in Medeo, but failed to qualifying for the final distance. The following year, he finish 8th in the same tournament (after a 15th in the Europeans) placing second in the 1500 m. His breakthrough came in 1990, winning the World Championships in Innsbruck, Austria. The following four years, he would win two more World titles (1991 and 1994), finishing 2nd in 1993 and 3rd in 1992. He won the European Championships in 1991 and finished 3rd in the next three editions.
Koss made his Olympic debut in 1992, finished 7th in the 5000 m, five days after undergoing surgery because of an inflamed pancreas. He would recover to win gold in the 1500 m (by only 0.04 seconds over countryman Ådne Søndrål) and silver in the 10000 m (behind Geir Karlstad, another Norwegian).
After his career, Koss became a UNICEF ambassador and a member of the International Olympic Committee (until 2002).