A method of operating a semiconductor memory device includes checking an erase-program cycling number, setting a target erase level to be maintained when the erase-program cycling number is less than a predetermined critical number, and setting the target erase level to be increased when the erase-program cycling number is greater than or equal to the predetermined critical number, and performing an erase operation so that threshold voltages of selected memory cells are less than the set target erase level.