We know from fossil evidence that Neanderthals evolved in Europe around 400,000 years ago, and later (~150,000 years ago) spread into western Asia, before disappearing from all areas in their range about 30,000 years ago. However, it can sometimes be quite hard to be certain whether or not a fossil is from a Neanderthal, which has limited scientists' understanding of the species' distribution and the timespan during which it lived.
Molecular biology to the rescue! (I read a comment today, on another blog, noting that in many research areas molecular biology, rather than fossil data, is the leading tool for our understanding of evolutionary change.)
A team led by Johannes Krause (2007) used mtDNA sequences to help them examine the geographical range of Neanderthals. They obtained DNA from two lots of remains: those of a child from an Uzbekistan cave (the Teshik-Tash remains), and sub-adult bones from Okladnikov cave in the Altai region of Siberia (found in association with Mousterian tools and dated to between 37,720 & 43,700 years ago). Both lots of bones are very fragmentary and there has been some argument over whether they belong to sapiens or neandertalensis. Krause & his co-workers hoped to solve the problem by obtaining mtDNA from the Teshik-Tash & Okladnikov bones, which could then be compared with mtDNA sequences already obtained by other workers from 13 confirmed Neanderthal individuals from Europe.
Once they'd been successful in getting mtDNA from the bones, the team used PCR to amplify this to useable amounts, and then had to distinguish any Neanderthal mtDNA that might be present from modern human mtDNA contamination (& you would expect a fair amount from a fossil that's been excavated and handled during study). They ended up with 2 mtDNA sequences that strongly resembled previously published Neanderthal mtDNA. Their conclusion: both individuals were indeed neandertalensis, and not sapiens. And their results were confirmed by independent analysis by another research team.
So it really does look like Neanderthals had a more extensive range than previously thought.
J. Krause et al. (2007) Neanderthals in central Asia and Siberia. Nature 449: 902-904