A method of operating a memory device that includes a plurality of stages each having a plurality of page buffers. The method including performing a verify operation of a first program loop from among a plurality of program loops, the verify operation of the first program loop including, performing a first off-cell counting operation on a first stage of the plurality of stages based on a first sampling rate to generate a first off-cell counting result; selectively changing the first sampling rate based on the first off-cell counting result to generate a changed first sampling rate; and performing a second off-cell counting operation on a second stage of the plurality of stages based on one of the first sampling rate and the changed first sampling rate to generate a second off-cell counting result.