According to one embodiment, a nonvolatile semiconductor memory device includes a memory cell array and a control circuit configured to repeat a program operation and a verify operation. The control circuit performs a first verify operation of sensing whether threshold voltages of selected memory cells are greater than or equal to a first threshold voltage, and a second verify operation of sensing whether the threshold voltages of the selected memory cells are greater than or equal to a second threshold voltage (first threshold voltage