This study attempts to elaborate a chronology of rock art in the Russian and Mongolian part of the Altai Mountains, from the Paleolithic to the Late Middle Ages. We focus on the style and themes of rock art and on petroglyphic palimpsests. The earliest representations date to the Upper Paleolithic. On certain palimpsests, images of horses in the Kalguty style are overlaid by Bronze Age petroglyphs. The key challenge is to identify Neolithic petroglyphs. Among the huge number of Bronze Age representations, some follow the traditions peculiar to the Afanasyevo and Chemurchek cultures. The key feature of the latter is so-called “Chemurchek anthropomorphs”. Bronze Age petroglyphs, representing animals, humans, weapons, wheeled vehicles, etc., are chronologically and culturally diverse and must be subdivided respectively. Early Iron Age ones require attribution to either the initial stage or to the mid-1st millennium BC. We discuss the difficulties of analyzing rock art of the Xiongnu-Sarmatian age, the expressive Turkic style, that of the early medieval rock art, and recent petroglyphs of the southern Russian Altai.