A method controlling the execution of a reliability verification operation in a storage device including a nonvolatile memory device includes; determining whether a read count for a designated unit within the nonvolatile memory device exceeds a count value limit, and upon determining that the read count exceeds the count value limit, executing the reliability verification operation directed to the designated unit, wherein the count value limit is based on at least one of read count information, page bitmap information and environment information stored in the storage device.