The universe is magnetized on all scales probed so far. On the largest scales, galaxies and galaxy clusters host magnetic fields at the micro Gauss level coherent on scales up to ten kpc. Recent observational evidence suggests that even the intergalactic medium in voids could host a weak ∼ 10(-16) Gauss magnetic field, coherent on Mpc scales. An intriguing possibility is that these observed magnetic fields are a relic from the early universe, albeit one which has been subsequently amplified and maintained by a dynamo in collapsed objects. We review here the origin, evolution and signatures of primordial magnetic fields. After a brief summary of magnetohydrodynamics in the expanding universe, we turn to magnetic field generation during inflation and phase transitions. We trace the linear and nonlinear evolution of the generated primordial fields through the radiation era, including viscous effects. Sensitive observational signatures of primordial magnetic fields on the cosmic microwave background, including current constraints from Planck, are discussed. After recombination, primordial magnetic fields could strongly influence structure formation, especially on dwarf galaxy scales. The resulting signatures on reionization, the redshifted 21 cm line, weak lensing and the Lyman-α forest are outlined. Constraints from radio and γ-ray astronomy are summarized. Astrophysical batteries and the role of dynamos in reshaping the primordial field are briefly considered. The review ends with some final thoughts on primordial magnetic fields.