A semiconductor memory device in accordance with an embodiment includes: a memory cell array having memory cells disposed at respective intersections of first lines and second lines; and a control circuit configured to apply a first pulse voltage multiple times to selected one of the first lines and selected one of the second lines, such that a certain potential difference is applied to a selected memory cell thereby causing transition of a resistance state. The control circuit is configured to, when the selected memory cell is not caused to undergo transition of the resistance state even after application of the first pulse voltage a certain number of times, execute a rescue operation where a second pulse voltage is applied to the selected memory cell subsequent to application of the first pulse voltage, the second pulse voltage having a pulse width longer than that of the first pulse voltage.