A storage device includes a nonvolatile memory device and a controller. A nonvolatile memory device includes a plurality of memory blocks. Each of the plurality of memory blocks is divided into a plurality of zones and is formed on a substrate. Each of the plurality of zones comprises one or more word lines. A controller performs a reliability verification read operation on a first zone of the plurality of zones of a memory block selected from the plurality of memory blocks if a number of read operations performed on the first zone reaches a first threshold value and performs the reliability verification read operation on a second zone of the plurality of zones of the selected memory block if a number of read operations performed on the second zone reaches a second threshold value.