Understanding the formation of the first stars is one of the frontier topics in modern astrophysics and cosmology. Their emergence signalled 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 Λ cold dark matter (ΛCDM) 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⊙ 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. Foremost among them are predictions for the upcoming James Webb space telescope (JWST), to be launched ~2018, and for 'stellar archaeology', which probes the abundance pattern in the oldest, most-metal poor stars in our cosmic neighborhood, thereby constraining the nucleosynthesis inside the first supernovae.