Provided herein may be a memory device and a method of operating the memory device. The memory device includes an operation code generator configured to generate a program code and a verify code in response to a program control code and to output an operation code using the program code and the verify code, a verify counter configured to store a count value acquired by counting the number of verify operations that are performed depending on the verify code, a verify determiner configured to compare the count value with a reference value depending on the result of the verify operation and to generate the program control code to change a step voltage for raising a program voltage depending on the comparison result, and a voltage generator configured to generate the program voltage and a verify voltage depending on the operation code.