We study the nucleation of blebs, i.e., protrusions arising from a local detachment of the membrane from the cortex of a cell. Based on a simple model of elastic linkers with force-dependent kinetics, we show that bleb nucleation is governed by membrane peeling. By this mechanism, the growth or shrinkage of a detached membrane patch is completely determined by the linker kinetics, regardless of the energetic cost of the detachment. We predict the critical nucleation radius for membrane peeling and the corresponding effective energy barrier. These may be typically smaller than those predicted by classical nucleation theory, implying a much faster nucleation. We also perform simulations of a continuum stochastic model of membrane-cortex adhesion to obtain the statistics of bleb nucleation times as a function of the stress on the membrane. The determinant role of membrane peeling changes our understanding of bleb nucleation and opens new directions in the study of blebs.