A storage device includes a nonvolatile memory device including memory blocks and a controller configured to control the nonvolatile memory device. Each of the memory blocks includes a plurality of cell strings each including at least one selection transistor and a plurality of memory cells stacked on a substrate in a direction perpendicular to the substrate. The controller controls the nonvolatile memory device to perform a read operation on some of selection transistors of a selected one of the memory blocks and to perform a program operation on the selection transistors of the selected memory block according to a result of the read operation.