Sequences from the mitochondrial DNA (mtDNA) control region were analyzed in nine European and West Asian populations. They showed low genetic heterogeneity when compared to world populations. However, a Caucasoid population tree displayed a robust east-west gradient. Within-population diversity (ascertained through various parameters) and mean pairwise differences declined from east to west, in a pattern compatible with ancient population migration and expansion from the Middle East. Estimated expansion times indicate a Paleolithic event with important differences among populations according to their geographical position and thus a slower tempo than previously believed. The replacement of Neanderthals by anatomically modern humans, fully compatible with the present results, may have been a slower and more complex process than cultural change suggests.