Techniques are disclosed herein for erasing non-volatile memory cells. A subset of the memory cells are pre-conditioned prior to erase. The pre-conditioning alters the threshold voltage of the memory cells in a way that may help make later calculations more accurate. As an example, memory cells along a single word line might be pre-conditioned. After the pre-conditioning, the memory cells are erased using a trial erase pulse. A suitable magnitude for a second pulse is determined based on the magnitude of the trial erase pulse and data collected about the threshold voltage distribution after the trial erase. The second erase pulse is used to erase the memory cells. Determining an appropriate magnitude for the second erase pulse minimizes or eliminates over-erasing.