Neanderthals were once widespread across Europe and western Asia. They also penetrated into the Altai Mountains of southern Siberia, but the geographical origin of these populations and the timing of their dispersal have remained elusive. Here we describe an archaeological assemblage from Chagyrskaya Cave, situated in the Altai foothills, where around 90,000 Middle Paleolithic artifacts and 74 Neanderthal remains have been recovered from deposits dating to between 59 and 49 thousand years ago (age range at 95.4% probability). Environmental reconstructions suggest that the Chagyrskaya hominins were adapted to the dry steppe and hunted bison. Their distinctive toolkit closely resembles Micoquian assemblages from central and eastern Europe, including the northern Caucasus, more than 3,000 kilometers to the west of Chagyrskaya Cave. At other Altai sites, evidence of earlier Neanderthal populations lacking associated Micoquian-like artifacts implies two or more Neanderthal incursions into this region. We identify eastern Europe as the most probable ancestral source region for the Chagyrskaya toolmakers, supported by DNA results linking the Neanderthal remains with populations in northern Croatia and the northern Caucasus, and providing a rare example of a long-distance, intercontinental population movement associated with a distinctive Paleolithic toolkit.