A storage device includes a nonvolatile memory device and a memory controller. After writing first data at the first page, the memory controller writes second data at a second page. The memory controller generates first check data corresponding to the first data and second check data corresponding to the second data. The memory controller recovers the first and second physical addresses and the first and second logical addresses based on the second check data.