Understanding the formation of the first stars is one of the frontier topics in modern astrophysics and cosmology. Their emergence signaled the end of the cosmic dark ages, a few hundred million years after the Big Bang, leading to a fundamental transformation of the early Universe through the production of ionizing photons and the initial enrichment with heavy chemical elements. We here review the state of our knowledge, separating the well understood elements of our emerging picture from those where more work is required. Primordial star formation is unique in that its initial conditions can be directly inferred from the Lambda Cold Dark Matter (LCDM) model of cosmological structure formation. Combined with gas cooling that is mediated via molecular hydrogen, one can robustly identify the regions of primordial star formation, the so-called minihalos, having total masses of ~10^6 M_sun and collapsing at redshifts z~20-30. Within this framework, a number of studies have defined a preliminary standard model, with the main result that the first stars were predominantly massive. This model has recently been modified to include a ubiquitous mode of fragmentation in the protostellar disks, such that the typical outcome of primordial star formation may be the formation of a binary or small multiple stellar system. We will also discuss extensions to this standard picture due to the presence of dynamically significant magnetic fields, of heating from self-annihalating WIMP dark matter, or cosmic rays. We conclude by discussing possible strategies to empirically test our theoretical models.

Review, revised version; now in print, Rep. Prog. Phys. (2013), 52 pages, 14 figures (for high-resolution, please see the journal)