Fjellström started his career at local Umeå club Gimonäs CK. After the bigger clubs noticed his skills he moved to Stockholm and Djurgårdens IF. He remained at Djurgården for five seasons before moving to Malmö FF. He enjoyed much success at the club and went on a loan to Dalian Wanda in China before playing a final season in Malmö. Fjellström decided to end his career after a knee injury had made him miss a season after which he thought that he couldn't perform at the same level as before his injury.