Gravitational waves (GWs) have a great potential to probe cosmology. We review early universe sources that can lead to cosmological backgrounds of GWs. We begin by presenting definitions of GWs in flat space-time and in a cosmological setting, and discussing the reasons why GW backgrounds from the early universe are of a stochastic nature. We recap current observational constraints on stochastic backgrounds, and discuss some of the characteristics of present and future GW detectors including advanced LIGO, advanced Virgo, the Einstein Telescope, KAGRA, LISA. We then review in detail early universe GW generation mechanisms proposed in the literature, as well as the properties of the GW backgrounds they give rise to. We classify the backgrounds in five categories: GWs from quantum vacuum fluctuations during standard slow-roll inflation, GWs from processes that operate within extensions of the standard inflationary paradigm, GWs from post-inflationary preheating and related non-perturbative phenomena, GWs from first order phase transitions (related or not to the electroweak symmetry breaking), and GWs from topological defects, in particular from cosmic strings. The phenomenology of early universe processes that can generate a stochastic background of GWs is extremely rich, and some backgrounds are within the reach of near-future GW detectors. A future detection of any of these backgrounds will provide crucial information on the underlying high energy theory describing the early universe, probing energy scales well beyond the reach of particle accelerators.