A nonvolatile semiconductor memory device includes a memory cell array having nonvolatile memory cells in which one of multiple values is programmable therein by setting one of a plurality of threshold values therein and a control circuit that performs a writing operation on the memory cells. The writing operation performed by the control circuit includes a pre-programming verification operation to determine a threshold level of a memory cell in an erasure state, and a program operation in which a program voltage is selected from a plurality of program voltages on the basis of a determination result of the pre-programming verification operation.