At the 1999 World Cup in Hasliberg , Lebedew made his first international appearance. He made his debut in the Freestyle World Cup on January 12, 2002 in Mont-Tremblant , where he finished 22nd and immediately won his first World Cup points. He was also able to qualify for the 2002 Winter Olympics, where he achieved his best result to date with 14th place. As fourth of the World Cup jumping in Lake Placid , he made it to the top of the world for the first time on January 17, 2003. In the winter of 2003/04, a 7th place remained his best result.
After a cautious start to the season, Lebedev achieved the first World Cup podium on March 11, 2005 when he jumped to 3rd place in Madonna di Campiglio . At the end of the season he won his first Russian championship title. His results during the 2005/06 World Cup season did not suggest a success at the 2006 Winter Olympics . At the Olympic jumping in Sauze d'Oulx , however, he surprised by winning the bronze medal, behind the Chinese Han Xiaopeng and the Belarusian Dzmitryj Daschtschynski .
A 5th place was Lebedew's best result in the 2006/07 World Cup season. In fourth place at the 2007 World Cup in Madonna di Campiglio , he just missed a medal. The so far best World Cup result he achieved on February 1, 2008 with 2nd place in Deer Valley . After a tough 2008/09 season, he won the Russian championship for the second time. Due to injury, Lebedev had to pause the entire 2009/10 season, in 2011 he did not get beyond a 16th place.