Alexei Boltenko first appeared internationally with a ninth place in the sprint at the Junior World Championships in 1998. In 1999 he placed himself in the front of the juniors, this time eleventh in the sprint and thirteenth in the pursuit. Among the active players he was in action for the first time in December 2004 at the European Cup sprint in Obertilliach and was 41st, on the following weekend he was 23rd and 25th in the sprint and pursuit in the points. During the 2004/2005 season he was used at the 2005 European Championships in Novosibirsk , which were the most successful competitions of his career. In the sprint and in the pursuit he was third and as the starting runner of the relay together with Sergej Balandin , Pawel Rostovzew and Dmitri Yaroshenko European champion. In 2005 he was also the Russian team champion. A year later - again in Obertilliach - he achieved the first top ten results in eighth and fifth in the sprint and pursuit and was also in the top twenty twice in Windischgarsten . Then he was no longer used in the European Cup, although he was included in the funding program for the 2006 Olympic Games in Turin.