Lehtinen played his entire 15-year National Hockey League (NHL) career with the organization after the franchise moved to Dallas in 1993.

He spent another year with Kiekko-Espoo, but the team struggled, and after one season, Lehtinen received an offer from one of the biggest clubs in Finland at the time, TPS in Turku.

Lehtinen was immediately paired with another future NHLer, Saku Koivu, and the two formed an integral part of TPS's great season.

[citation needed] After an impressive year in 1995, where Lehtinen won both the SM-liiga and World Championship, he went overseas to play in the NHL.

Lehtinen worked his way up in three years to join Mike Modano on the team's first line and was nominated for the Frank J. Selke Trophy for the first time in 1996–97 season.

Lehtinen's fellow countrymen Saku Koivu, Teemu Selänne and Jari Kurri were also voted to the Game.

The same year, Lehtinen was again a nominee for the Selke Trophy as the best defensive forward and eventually won the prestigious award.

That year, Lehtinen set career-high statistics and also captured the Selke Trophy, becoming just the third player in NHL history to win the award in consecutive seasons.

Although they again made the playoffs, the Stars, however, did not progress go as deep as they had in previous years and were dispatched in the second round by the St. Louis Blues in a four-game sweep.

Although the Stars failed to qualify for the 2002 playoffs, Lehtinen managed to score 25 goals, 24 assists and finished first on the team in plus-minus with +27.

The 2003–04 season, was a disappointment to Lehtinen, as injury problems to his knee allowed him to play just 58 games, where he scored 26 points.

Lehtinen began the 2007–08 season strongly, posting six goals and 13 assists (19 points) in just 21 games before suffering a sports hernia.

On December 8, 2010, Lehtinen officially announced his retirement from professional hockey,[3] finishing with 243 goals and 271 assists and a career plus-minus rating of +176 in 875 NHL games, all with the Stars.

The two were married in June 1998 and since the ceremony was only a few days after the NHL Awards, Lehtinen was not present to accept the first Frank J. Selke Trophy of his career.