A storage device includes a nonvolatile memory device including a plurality of memory blocks, each including a plurality of memory cells connected to a plurality of word lines, and a controller configured to perform a first read operation on memory cells connected to a selected word line included in a selected memory block based on a request of an external host device. The controller is further configured to perform a check read operation that checks a reliability of the memory cells of the selected memory block after performing the first read operation. In the check read operation, the controller is further configured to select and perform one of an actual check and a machine learning-based check.