A method of operating a semiconductor memory device includes performing a first program operation in order to raise threshold voltages of memory cells, performing a program verification operation for detecting fast program memory cells, each having a threshold voltage risen higher than a first sub-verification voltage from a second sub-verification voltage or lower, by using a target verification voltage and the first sub-verification voltage and the second sub-verification voltage which are sequentially lower than the target verification voltage, and performing a second program operation under a condition that an increment of each of threshold voltages of memory cells, which is lower than the target verification voltage, is greater than an increment of the threshold voltage of each of the fast program memory cells.