In a method of erasing a nonvolatile memory device, an erase operation is performed on memory cells of a selected block. A first soft program operation is performed on the cells on which the erase operation has been performed. The erase operation and the first soft program operation are repeatedly performed by increasing an erase voltage by a first step voltage until a threshold voltage of the memory cells becomes lower than a first erase verify voltage. When the threshold voltage of the memory cells becomes lower than the first erase verify voltage, a second soft program operation is performed. The second soft program operation is repeatedly performed by increasing a soft program voltage by a second step voltage until a cell is programmed to have a soft program verify voltage.