After his first professional season in his native Russia, with SKA Saint Petersburg in the then Russian Superleague in the 2000–01 season, Tyutin impressed as a rookie as was selected by the Rangers in the 2001 NHL Entry Draft. On the back of his selection, Tyutin opted to return to the junior level and play one major junior CHL season with the Guelph Storm of the Ontario Hockey League. In the 2001–02 season with the Storm, Tyutin was a standout on the blueline, earning rookie of the month honours in November and leading the club amongst defenseman in scoring with 59 points in just 53 games to earn selection to the OHL and CHL All-Rookie Teams. After one season in the OHL, Tyutin opted to return to continue his development in the Russian Superleague with Saint Petersburg and later Ak Bars Kazan. Tyutin started his North American professional career with the Hartford Wolf Pack, the American Hockey League affiliate of the New York Rangers at the start of the 2003–04 season. Tyutin made his NHL debut with the New York Rangers on 12 February 2004 against the Philadelphia Flyers. He recorded his first point four days later with an assist in a game against the Ottawa Senators. Nearly a month later, on 13 March 2004, Tyutin scored his first NHL goal, a shorthanded goal, against Roberto Luongo of the Florida Panthers. On 21 March 2004, he had his first multi-point game with two assists against the Pittsburgh Penguins. He began the 2004–05 season, during the NHL lockout, with the Hartford Wolfpack. In 13 games, he tallied two goals, one assist, and ten penalty minutes. After his brief stint with the Wolfpack, Tyutin returned to Russia to play in the Russian Superleague for his old team, SKA Saint Petersburg. Tyutin rejoined the Rangers for the start of the 2005–06 NHL season, he skated in 77 games with the Rangers, registering six goals and 19 assists for 25 points, along with 58 penalty minutes. Among team defensemen, he ranked first in power play goals, tied for first in goals and was second in scoring with 25 points. On 2 August 2006, Tyutin signed a two-year contract extension with the New York Rangers. On 17 February 2008, Tyutin signed a four-year contract extension with the Rangers worth $11.375 million. In the immediate off-season, on 2 July 2008, Tyutin was traded with Christian Bäckman to the Columbus Blue Jackets for Nikolai Zherdev and Dan Fritsche. He scored nine goals as well as adding 25 assists in his first season in Columbus. On 31 August 2011, Tyutin signed a six-year contract extension with the Columbus Blue Jackets worth $27 million. During the 2012–13 NHL lockout, Tyutin played for Atlant Moscow of the Kontinental Hockey League. After playing 8 seasons with the Blue Jackets, on 29 June 2016, the Blue Jackets bought out the remaining two-years of Tyutin's contract in order to clear salary cap space, as the team was pressed against the cap ceiling. He immediately became a free agent. On 1 July 2016, Tyutin was quickly signed on the opening day of free agency, agreeing to a one-year, $2 million contract to add a veteran presence for the Colorado Avalanche. Signed with the intention of mentoring and playing alongside young countryman Nikita Zadorov, Tyutin began the 2016–17 season making his Avalanche debut in a 6–5 opening night victory over the Dallas Stars on 15 October 2016. He collected his first goal for the club, in a 3–1 defeat to the Florida Panthers on 16 December 2016.
Tyutin played for the Russian national team at the 2006, 2010, and 2014 Winter Olympics. He recorded one assist along with four penalty minutes in eight games in 2006, two assists in four games in 2010, and no points in five games in 2014. Tyutin also played for Russia at three World Championships, winning gold in 2008.