Khodchenkova was born in Moscow, Russian SFSR, Soviet Union. She became known after starring in Stanislav Govorukhin's movie Bless the Woman (2003), for which she received a nomination for the Nika Award and continued her career with the role of clairvoyant Cassandra in the historic television series Mascot Love (2005).
In 2008, she won the award Polish Film Festival for Best Actress in Little Moscow. She is also known for her roles in box office films Love in the City (2009), its sequel, Love in the City 2 (2010) and Office Romance. Our Time (2011). She currently stars in the TV series Lavrova's Method, and appears as Irina in Tinker Tailor Soldier Spy (2011). She co-starred with Hugh Jackman in the 2013 superhero film The Wolverine as Viper, one of the film's main antagonists. Her performance received negative reviews, as it was "supposedly" revealed that producers were disappointed with Khodchenkova's performance, so they cut her screen time drastically. It was also reported that all her lines were dubbed by a voice-actress as she couldn't perfect a strong enough American accent.