The semiconductor memory device includes a memory cell block including a plurality of memory cells, a peripheral circuit section configured to perform an erase loop including a supply operation supplying an erase voltage and an erase verification operation to erase data stored in the memory cells, a fail bit counter configured to count the number of memory cells not erased in an erase operation among the memory cells to generate a count signal based on a fail count corresponding to a counting result in the erase verification operation, and a controller configured to control the peripheral circuit section to set a new erase voltage by increasing an erase voltage, used in a previous erase loop, by a first step voltage or decreasing the erase voltage by a second step voltage based on the fail count, and perform the erase loop using the new erase voltage.