The emergence of the first sources of light at redshifts of z˜10-30 signaled the transition from the simple initial state of the Universe to one of increasing complexity. Recent progress in our understanding of the formation of the first stars and galaxies, starting with cosmological initial conditions, primordial gas cooling, and subsequent collapse and fragmentation are reviewed. The important open question of how the pristine gas was enriched with heavy chemical elements in the wake of the first supernovae is emphasized. The review concludes by discussing how the chemical abundance patterns conceivably allow us to probe the properties of the first stars, and allow us to test models of early metal enrichment.