D'ençà de mitjan segle xviii, ja hi havia un poble anomenat Txesnokovka on actualment hi ha la ciutat de Novoaltaisk. La construcció de la línia ferroviària de l'Altai Novossibirsk-Barnaül-Semipalatinsk fou inaugurada el 1915. Txesnokovka accedí a l'estatus d'entitat urbana el 1936. El 1942 Txesnokovka obtingué l'estatus de ciutat i el 1962 fou rebatejada Novoaltaisk.