Together with Sten Stensen, Jan Egil Storholt and Amund Sjøbrend, Kay Arne Stenshjemmet formed the "Four S-es" of Norwegian speed skating in the 1970s. A bronze medallist at the 1973 World Junior Championships, Stenshjemmet had his senior breakthrough in 1976 by winning that year's European Championships by the tiny margin of 0.005 points. He remained a top-5 skater in the following years, always facing tough competition from the unbeatable Eric Heiden and his Norwegian colleagues. Stenshjemmet won his second European title in 1980, adding two silvers (1977, 1979) and one bronze (1981) to the collection. At World Championships, he was less successful, his best being second in 1981, with a third in 1979. After a failed Olympic appearance in Innsbruck 1976, Stenshjemmet's 1980 Lake Placid appearance was much rememberable, as he brought home two silver medals from the 1,500 and 5,000 metres, both times beaten by Heiden. In 1977, he lowered the 5,000 m world record under 7 minutes\: 6:56.9 (although Sergey Marchuk had broken the 7-minute barrier earlier in the same race). In national competition, Stenshjemmet was crowned Norwegian champion five times, four times in allround (1976-78 and 1981) and once in sprint (1976).
Personal Bests\: 500 – 38.2 (1981); 1000 – 1:17.5 (1981); 1500 – 1:56.18 (1981); 5000 – 6:56.9 (1977); 10000 – 14:57.30 (1980).