A storage device may include a memory device including a memory block coupled to physical word lines each including pages, and a memory controller configured to control the memory device such that, in response to a power off event occurring during a program operation on a selected page, fine program operations are performed on to-be completed pages, which precede the selected page, on which foggy program operations have been completed and on which the fine program operations have not yet been performed. The program operation may include a foggy program operation of programming memory cells included in the pages so that each memory cell has a threshold voltage corresponding to any one of intermediate states corresponding to states, and a fine program operation of programming the memory cells having the threshold voltages corresponding to the intermediate states so that each memory cell has a threshold voltage corresponding to any one state.