A semiconductor memory device and a method of operating the same are provided. The method includes performing an overall erase operation such that each threshold voltage of all memory cells connected to even word lines and odd word lines in a selected memory cell block are lower than a first target level, performing an erase operation such that each threshold voltage of the memory cells connected to the even word lines are lower than a second target level which is lower than the first target level, and performing an erase operation such that each threshold voltage of the memory cells connected to the odd word lines are lower than the second target level.