Ecosystem regime shifts are conceived as abrupt global transitions from one stable state to an alternative stable state, induced by slow environmental changes. Spatially extended ecosystems, however, can also respond to local disturbances by the nucleation of small domains of the alternative state. Such a response can lead to gradual regime shifts involving front propagation and coalescence of alternative-state domains. When one of the states is spatially patterned a multitude of intermediate stable states appears, giving rise to step-like gradual shifts with extended pauses at these states. Using this observation we propose a new early indicator for impending regime shifts that becomes effective earlier than current suggested indicators - temporal decrease of spatial correlation lengths. Our results are particularly relevant to desertification in drylands where transitions to bare soil take place from spotted vegetation and the degradation process often involves step-like events of local vegetation mortality caused by repeated droughts.