To resolve the phylogeny of certain mitochondrial DNA (mtDNA) haplogroups in eastern Europe and estimate their evolutionary age, a total of 73 samples representing mitochondrial haplogroups U4, HV*, and R1 were selected for complete mitochondrial genome sequencing from a collection of about 2,000 control region sequences sampled in eastern (Russians, Belorussians, and Ukrainians) and western (Poles, Czechs, and Slovaks) Slavs. On the basis of whole-genome resolution, we fully characterized a number of haplogroups (HV3, HV4, U4a1, U4a2, U4a3, U4b, U4c, U4d, and R1a) that were previously described only partially. Our findings demonstrate that haplogroups HV3, HV4, and U4a1 could be traced back to the pre-Neolithic times ( approximately 12,000-19,000 years before present [YBP]) in eastern Europe. In addition, an ancient connection between the Caucasus/Europe and India has been revealed by analysis of haplogroup R1 diversity, with a split between the Indian and Caucasus/European R1a lineages occurring about 16,500 years ago. Meanwhile, some mtDNA subgroups detected in Slavs (such as U4a2a, U4a2*, HV3a, and R1a1) are definitely younger being dated between 6,400 and 8,200 YBP. However, robust age estimations appear to be problematic due to the high ratios of nonsynonymous to synonymous substitutions found in young mtDNA subclusters.