A semiconductor memory device according to an embodiment includes memory cell transistors, a word line, and a controller. A memory cell transistor whose threshold voltage is included in first and second states store first and second data, respectively. In a verify operation of the first data, during application of a verify high voltage of the first data to the word line, the controller is configured to determine whether or not a threshold voltage of a memory cell transistor to which the first data is to be written exceeds the verify high voltage of the first data, and also determine whether or not a threshold voltage of a memory cell transistor to which the second data is to be written exceeds a verify low voltage of the second data.