Soft glassy materials such as mayonnaise, wet clays, or dense microgels display a solid-to-liquid transition under external shear. Such a shear-induced transition is often associated with a nonmonotonic stress response in the form of a stress maximum referred to as “stress overshoot.” This ubiquitous phenomenon is characterized by the coordinates of the maximum in terms of stress σM and strain γM that both increase as weak power laws of the applied shear rate. Here we rationalize such power-law scalings using a continuum model that predicts two different regimes in the limit of low and high applied shear rates. The corresponding exponents are directly linked to the steady-state rheology and are both associated with the nucleation and growth dynamics of a fluidized region. Our work offers a consistent framework for predicting the transient response of soft glassy materials upon startup of shear from the local flow behavior to the global rheological observables.