The concept of k-step full backward extension for subnormal operators is adapted to the context of completely hyperexpansive operators. The question of existence of k-step full backward extension is solved within this class of operators with the help of an operator version of the Levy-Khinchin formula. Some new phenomena in comparison with subnormal operators are found and related classes of operators are discussed as well.