A memory device may include: memory cells each having any one of first and second programmed states as a target programmed state; a peripheral circuit configured to perform a program operation so that each memory cell has a threshold voltage corresponding to the target programmed state; and a control circuit configured to control the peripheral circuit. The control circuit may include a program operation controller configured to control the peripheral circuit so that, during the program operation, an intermediate program operation is performed on the memory cells using an intermediate verify voltage, an additional program operation is performed on memory cells each having the second programmed state as a target programmed state if an intermediate verify operation passes, and a final program operation is performed on the memory cells such that each memory cell has a threshold voltage corresponding to the target programmed state.