I have seen a show on PBS, a Nova episode I think, on Neanderthals. They have managed to recover some mitochondrial DNA from some late specimens. This DNA shows the earliest common ancestor with modern humans to be about 250,000 years ago. I may be off on the date, but it was well before modern humans existed.
Another PBS special followed the work of one man on the migrations out of Africa. His work used the y chromosome. It showed an early migration through southern Asia and into Australia. A second, larger migration moved into central Asia, then split east and west, filling Asia and Europe.