Disclosed is a semiconductor memory device and a method of operating the same. The semiconductor memory device includes a memory cell array including a plurality of memory blocks, a peripheral circuit configured to perform an erase characteristic check operation and an erase operation on the plurality of memory blocks. The semiconductor memory device also includes a control circuit configured to control the peripheral circuit to perform the erase characteristic check operation and the erase operation, determine whether each of the plurality of memory blocks has a normal erase characteristic or an overerase characteristic according to a result of the erase characteristic check operation for each of the plurality of memory blocks, and set an erase voltage of the erase operation based on the determined erase characteristic according to the result of the erase characteristic check operation.