Several emerging links between high-redshift observational cosmology, and the Galactic fossil evidence found in the kinematics, metallicities and ages of Milky Way stars are discussed. In a flat Cold Dark Matter model with Omega similar or equal to 0.3 that agrees with present large-scale structure observations, the oldest stars in the Milky Way should have formed in the first halos where gas was able to cool, at z similar or equal to 20. These earliest, weakly bound dwarf galaxies probably turned only a small fraction of their gas to stars, which should be metal-poor. However, the merging rate in the early universe was much faster than the present one, so massive halos with more efficient star formation and metallicities up to the highest values present today in the bulge could have formed less than 10(9) years after the oldest stars. The mean metallicity produced in the universe by a given redshift is related to the mean surface brightness of star-forming galaxies above this redshift, and also to the reionization epoch if galaxies were the dominant sources of ionizing radiation. The biased distribution of the early dwarf galaxies where the first stars formed should result in an age gradient with radius of the low-metallicity stars in the Milky Way, with the oldest ones concentrated in the bulge and the youngest in the outer halo.