He was born on 28 August 1972 in Moscow. After graduating from high school he studied biology for two years (1990 – 1991) at the Moscow State Pedagogical University (MPGU), then entered The Gerasimov Institute of Cinematography (VGIK) to study at the faculty of screenwriting and cinema studies (workshop of M.Vlasov).
In 1997, while studying at VGIK, he made a 20-minutes film MIMOKHOD - together with Alexey Popogrebsky. In 2001 he made a short film A CUNNING FROG.
His first feature-length film was KOKTEBEL, which he co-directed with Alexey Popogrebsky. In 2003 KOKTEBEL took part in the Moscow International Film Festival Main Competition program and won three prizes there: a MIFF Special Award, a FIPRESCI award and the award given by Russian film critics for the best debut movie. Khlebnikov's film A LONG AND HAPPY LIFE was selected for the main competition of Berlin International Film Festival.