Tärnström began his career with AIK IF of the Elitserien, with which he played 9 seasons as a pro, from 1992 to 2001. He then signed with the New York Islanders, who had drafted him 272th overall in the 1994 NHL Entry Draft. He played the most part of his first NHL season with the Isles, spending only a handful of games with the American Hockey League's Bridgeport Sound Tigers.
He ends up with the Pittsburgh Penguins the following season, where he becomes the team's top scorer, notching 52 points in 80 games, thus becoming the first defenseman in the team's history to lead it in points. He and the Pens' late season acquisition Richard Jackman become a deadly pair on the powerplay.