Hailing from Kristiansund, he started his career in local club Clausenengen, and played for another two small clubs Jerv and Nordlandet. He was then picked up by Brann, and later by Molde. At Molde he formed a partnership with Ole Gunnar Solskjær and Ole Bjørn Sundgot known as "the three S'es". He then played one season for Stabæk before going abroad with Helsingborg in Sweden. Playing under former Molde coach Åge Hareide, Stavrum became Allsvenskan top scorer in the 1998 season. He came to Scotland in 1999, joining Aberdeen.