A storage device includes a nonvolatile memory having a plurality of memory cells and a memory controller to control the nonvolatile memory. The operating method of the storage device includes reading previously programmed memory cells among the memory cells of the nonvolatile memory and determining a time after erase of the previously programmed memory cells, programming selected memory cells of the nonvolatile memory, and programming meta data including a time after erase of the selected memory cells, based on the determined time after erase of the previously programmed memory cells.