A nonvolatile semiconductor memory device according to an embodiment includes a control unit configured to perform a control of repeating a program operation, and a step-up operation, the program operation being an operation of applying a program pulse voltage to a selected memory cell and applying an intermediate voltage less than the program pulse voltage to first and second non-selected memory cells adjacent to the selected memory cell, and the step-up operation being an operation of increasing the program pulse voltage by a first step-up value. For a first period, the control unit maintains the intermediate voltage to be a constant value. For a second period, the control unit controls the step-up operation such that the intermediate voltage is increased by a second step-up value, and determines the first step-up value on the basis of the second step-up value.