A memory device includes a plurality of memory cells, a peripheral circuit, and a control logic. The peripheral circuit programs the plurality of memory cells to a program state among a plurality of program states. The control logic controls the peripheral circuit to perform a program verify operation for at least one program state among the plurality of program states, counts a bit number having a predetermined logic value by comparing a program verify voltage corresponding to a target program state in the at least one program state in a program verify operation for the target program state with threshold voltages of the plurality of memory cells, and determines a start time of a program verify operation for a program state higher than the target program state among the plurality of program states, based on the bit number having the predetermined logic value.