Markov was drafted by the Montreal Canadiens in the sixth round, 162nd overall, in the 1998 NHL Entry Draft. After being considered one of the best defencemen in Russia in 2000, he came over to North America and split time with the Canadiens and their then-minor league affiliate, the Quebec Citadelles of the American Hockey League. After rounding out his defensive game, he has become a regular in the Canadiens' starting line-up and is widely considered to be their most complete defenceman. During the 2004–05 NHL lockout, Markov played in his native Russia with Dynamo Moscow of the Russian Superleague. Markov signed a four-year contract with the Canadiens on 28 May 2007, keeping him with the team through the 2010–11 season. He had a career year in the 2007–08 season, and was selected to his first NHL All-Star Game as a starter, in Atlanta. in 2010 On 1 October 2009, Markov suffered a lacerated ankle injury after colliding with teammate Carey Price's skate and was initially expected to be out of the Canadiens' lineup until February 2010. Markov made a full recovery almost two months ahead of schedule and returned to action on 19 December 2009, when the Canadiens faced the New York Islanders. Markov ended up jump-starting the Habs' offence with two goals in his return en route to a 3–0 victory. During the 2010 Stanley Cup playoffs against the Pittsburgh Penguins on 30 April, Markov suffered a leg injury after being hit by Matt Cooke. On 16 July 2010, Markov became a Canadian citizen. During the 2010–11 season, he played only seven games, earning three points. On 13 November 2010, Markov suffered a knee injury in a game against the Carolina Hurricanes and underwent surgery 8 December 2010, missing the remainder of the season. On 23 June 2011, Markov signed a three-year contract with the Canadiens. On 10 March 2012, he played in his first game in over a year, tallying an assist in a 4–1 victory over the Vancouver Canucks. On 23 June 2014, Markov re-signed with the Canadiens to a three-year contract worth an annual average value of $5.75 million. On 15 September 2014, Markov was named an alternate captain for the Canadiens, along with P. K. Subban, Tomáš Plekanec and Max Pacioretty, sharing the leadership duties of a Canadiens squad currently without a team captain. On 18 September 2015, it was announced that Markov and Brendan Gallagher would serve as alternate captains for Max Pacioretty. On 26 July 2017 it was announced that Andrei Markov would not be returning to Montreal Canadiens for the 2017-2018 season after spending his entire NHL career with the team and playing 990 games over 16 years. Two days later, on 28 July, it was announced that Markov had agreed to a two-year deal with the KHL's Ak Bars Kazan. Markov's team would go on to win the Gagarin Cup in his first season in the KHL. On 16 April 2020 Andrei Markov announced his retirement from professional hockey.