Provided herein are a semiconductor memory device and a method of operating the semiconductor memory device. The semiconductor memory device having improved reliability includes a memory cell array including memory cells coupled to a plurality of word lines, a peripheral circuit configured to perform a program operation on a word line selected from among the plurality of word lines, and control logic configured to control the peripheral circuit so that, when the selected word line is a reference word line during the program operation, a partial erase operation is performed on memory cells included in a memory cell group corresponding to the reference word line.