Provided herein may be a semiconductor memory device and a method of operating the same. The semiconductor memory device may include a plurality of pages each including a plurality of memory cells, peripheral circuits configured to perform a program operation of a selected page among the plurality of pages and a control logic configured to control the peripheral circuits such that a main program operation is performed on the selected page and, when the main program operation is completed, a compensation program operation is performed on memory cells having lower threshold voltage retention characteristics compared to remaining memory cells, among the memory cells included in the selected page.