A nonvolatile semiconductor storage device according to an embodiment includes a write/erase unit, during data write or erase, the write/erase unit supplying a first electric pulse to a selected memory cell, the first electric pulse having an electric energy to an extent that an physical state of a memory element of the selected memory cell does not transition and accumulating charges in a rectifying element of the selected memory cell, after supplying the first electric pulse, and a certain pulse interval thereafter, and supplying a second electric pulse to the selected memory cell, the second electric pulse having larger electric energy than the first electric pulse, the second electric pulse causing the physical state of the memory element of the selected memory cell to transition.