A nonvolatile semiconductor storage device according to an embodiment includes an erase circuit executing an erase sequence, wherein in the erase sequence, the erase circuit executes: an erase operation to change a selection memory cell group to an erased state, after the erase operation, a soft program operation on the selection memory cell group to solve over-erased state, and after the soft program operation, a first soft program verification operation performed on at least one partial selection memory cell group of a first partial selection memory cell group and a second partial selection memory cell group so as to confirm whether the partial selection memory cell group includes a predetermined number of memory cells or more that have threshold values equal to or more than a predetermined first threshold value, and after the first soft program verification operation.