During his career, Kolodin has played for a number of Russian clubs. He started his career at FC Olimpia Volgograd where he remained for two years, scoring an impressive fourteen goals in 66 appearances before moving to FC Uralan in 2003. He made 44 appearances for the club and scored three goals. In 2004 he left for Krylia Sovetov, making 39 appearances and scoring two goals.
He moved to one of Russia's bigger clubs, Dynamo Moscow in 2005, and has had a successful time there, making 130 appearances and scoring fifteen goals along the way (as of 22 May 2012).
Kolodin got the chance to appear in his first major international tournament at Euro 2008. He played in all three of Russia's group D matches, against Spain, Sweden and Greece. In the quarter-finals against the Netherlands he received a yellow card mid-way through the second-half and was then shown a second yellow in the last minute, meaning a red card. However, the referee reversed his decision after consulting with his assistant on the basis that the ball had gone out of play before Kolodin committed the tackle. This was a controversial and much-debated decision at the time. Russia went on to win the match 3-1 in extra time.