Although Anatoly Shelyukhin concentrated on longer distances, he found his international fame in the shorter distances. Shelyukhin made his international début at the 1956 Olympics, where he was fifth in the 50 km and lost out in the 30 km by only a second to bronze medal winner Pavel Kolchin, thus settling for fourth place. At the 1957 World University Winter Games Shelyukhin won gold in the 30 km and relay, and silver in the 15 km. At the 1958 World Championships Shelyukhin won bronze at 15 km and a silver as a member of Soviet relay team. Shelyukhin made his last international appearance at the 1960 Olympics, where he won bronze as a member of the Soviet relay team and was 15th in the 30K. Domestically Shelyukhin won four Soviet Championships titles, one at 30 km in 1958 and three in the 50 km – in 1955, and 1958-59. After retiring from competition in 1962, Anatoly Shelyukhin worked the rest of his life as a cross-country skiing coach in his hometown Kostroma.