Kay Arne Stenshjemmet (born 9 August 1953) is a former speed skater from Norway.

Together with Amund Sjøbrend, Sten Stensen, and Jan Egil Storholt, Kay Stenshjemmet was one of the legendary four S-es (which sounds like "four aces" in Norwegian), four Norwegian top skaters in the 1970s and early 1980s.

On 19 March 1977, first Sergey Marchuk and then in the following pair Stenshjemmet were the first to skate the 5000 m below seven minutes, with 6:58.88 and 6:56.9, respectively.

Stenshjemmet's world record would last for five years, until Aleksandr Baranov skated 6:54.44.

At the 1980 Winter Olympics in Lake Placid, Stenshjemmet won silver on the 1500 m and on the 5000 m, both behind Eric Heiden.