In Sweden, Stenman started his career at Västerås SK. Later he moved to IF Elfsborg. He became a key player in there. However, Stenman played for IF Elfsborg for only a season and 2003, he moved again and went to Djurgårdens IF. His time at Djurgården he had won the Swedish double. He scored 8 goals for the club and his performance impressed the clubs outside Sweden. Finally, Bayer Leverkusen signed him for € 800 000 in November 2005. Yet, Stenman seemed to be too young for the German club. He played only a few matches.