It is generally accepted that the most ancient European mitochondrial haplogroup, U5, has evolved essentially in Europe. To resolve the phylogeny of this haplogroup, we completely sequenced 113 mitochondrial genomes (79 U5a and 34 U5b) of central and eastern Europeans (Czechs, Slovaks, Poles, Russians and Belorussians), and reconstructed a detailed phylogenetic tree, that incorporates previously published data. Molecular dating suggests that the coalescence time estimate for the U5 is approximately 25-30 thousand years (ky), and approximately 16-20 and approximately 20-24 ky for its subhaplogroups U5a and U5b, respectively. Phylogeographic analysis reveals that expansions of U5 subclusters started earlier in central and southern Europe, than in eastern Europe. In addition, during the Last Glacial Maximum central Europe (probably, the Carpathian Basin) apparently represented the area of intermingling between human flows from refugial zones in the Balkans, the Mediterranean coastline and the Pyrenees. Age estimations amounting for many U5 subclusters in eastern Europeans to approximately 15 ky ago and less are consistent with the view that during the Ice Age eastern Europe was an inhospitable place for modern humans.