An erase operation for non-volatile memory includes first and second phases. The first phase applies a series of voltage pulses to a substrate, where each erase pulse is followed by a verify operation. The verify operation uses a verify level which is offset higher from a final desired threshold voltage level. The erase pulses step up in amplitude until a maximum level is reached, at which point additional erase pulses at the maximum level are applied. The first phase ends when the verify operation passes. The second phase applies one or more extra erase pulses which are higher in amplitude than the last erase pulse in the first phase and which are not followed by a verify operation. This avoids the need to perform a verify operation at deep, negative threshold voltages levels, which can cause charge trapping which reduces write-erase endurance, while still achieving the desired deep erase.