Stoor was born in Stockholm, Sweden and started playing with Hammarby, who he joined in 1996 at the age of 12 as a youth player. In January 2001, he had a trial with Manchester United. During his professional career at the club he made 51 appearances and scored 2 goals from defence.
Stoor returned to Norway in January 2011, when he signed for Vålerenga as a free agent. After playing 15 matches for Vålerenga in Tippeligaen, Stoor was wanted by his old club Rosenborg ahead of the 2012 season, but he did not pass the medical test in Trondheim. Just before the Norwegian transfer window closed in March 2012, Fredrik joined Lillestrøm on a season-long loan-deal. His contract with Vålerenga was terminated ahead of the 2013 season, and Stoor subsequently signed a one-year contract with Lillestrøm.