The semiconductor memory device includes a memory cell array configured to include a plurality of blocks, wherein each of the blocks has pages and each of the pages includes memory cells, and a peripheral circuit configured to program the memory cells to target program states. Here, the peripheral circuit programs the memory cells to temporary program states by applying program voltages increasing step-by-step by a first incremental value, and then programs the memory cells to the target program states by applying program voltages increasing step-by-step by a second incremental value.