Morphological traits typical of Neanderthals began to appear in European hominids at least 400,000 years ago and about 150,000 years ago in western Asia. After their initial appearance, such traits increased in frequency and the extent to which they are expressed until they disappeared shortly after 30,000 years ago. However, because most fossil hominid remains are fragmentary, it can be difficult or impossible to determine unambiguously whether a fossil is of Neanderthal origin. This limits the ability to determine when and where Neanderthals lived. To determine how far to the east Neanderthals ranged, we determined mitochondrial DNA (mtDNA) sequences from hominid remains found in Uzbekistan and in the Altai region of southern Siberia. Here we show that the DNA sequences from these fossils fall within the European Neanderthal mtDNA variation. Thus, the geographic range of Neanderthals is likely to have extended at least 2,000 km further to the east than commonly assumed.