A semiconductor memory device is configured to perform a first verification operation by setting an initial voltage level of a verification voltage to a first voltage level and boosting the verification voltage during a first period. The semiconductor memory device includes a memory cell array that stores program data, a sensor generating sensing data, and a condition determination unit comparing the program data and the sensing data. A control logic unit includes a verification operation controller configured to selectively perform, based on a result of comparison of the program data and the sensing data, a first verification control operation for controlling a second verification operation by setting the initial voltage level to a second voltage level and boosting the verification voltage during a second period, and a second verification control operation for controlling the second verification operation by setting the initial voltage level to the first voltage level and boosting the verification voltage during the first period.