A non-volatile storage system that performs a multi-stage programming process to program non-volatile storage to a set of data threshold voltage distributions. The multi-stage programming process includes performing a first stage of the multi-stage programming process to change threshold voltages of at least a subset of the non-volatile storage elements from an erased distribution to one or more intermediate distributions, performing an intermediate stage of the multi-stage programming process to change threshold voltages of at least some of the non-volatile storage elements to appropriate distributions of the data threshold voltage distributions, and performing a later stage of the multi-stage programming process, after performing the intermediate stage of the multi-stage programming process, to tighten only a subset of the data threshold voltage distributions.