Disclosed are a semiconductor memory device and a method of operating the same. The semiconductor memory device includes a memory cell array including a plurality of memory cells which are programmed to a plurality of program states, a peripheral circuit configured to perform a program operation on the memory cell array, and a control logic configured to control the peripheral circuit to divide the plurality of program states into two or more program groups and sequentially program the two or more program groups during the program operation, wherein the control logic controls the peripheral circuit to simultaneously program the memory cells which are to be programmed to program states included in the same program group among the plurality of memory cells.