Nonvolatile memory devices support programming and verify operations that improve threshold-voltage distribution within programmed memory cells. This improvement is achieved by reducing a magnitude of the programming voltage steps and increasing a duration of the verify operations once at least one of the plurality of memory cells undergoing programming has been verified as a “passed” memory cell. The nonvolatile memory device includes an array of nonvolatile memory cells and a control circuit, which is electrically coupled to the array of nonvolatile memory cells. The control circuit is configured to perform a plurality of memory programming operations (P) by driving a selected word line in the array with a first stair step sequence of program voltages having first step height (e.g., ΔV1) and then, in response to verifying that at least one of the memory cells coupled to the selected word line is a passed memory cell, driving the selected word line with a second stair step sequence of program voltages having a second step height (e.g., ΔV2) lower than the first step height.