A storage device includes a nonvolatile memory device and a memory controller allowing the nonvolatile memory device to perform a read operation on memory cells belonging to a selected page in a selected memory block. After the read operation, the memory controller allows the nonvolatile memory device to perform a first check read operation on memory cells of a first neighbor page while sequentially selecting sets of read voltages. After the first check read operation, the memory controller allows the nonvolatile memory device to perform a second check read operation on memory cells of a second neighbor page while sequentially selecting the sets of read voltages. In the second check read operation, the memory controller first selects a set of read voltages, which are used in the first check read operation in which error correction succeeds.