A method of operating a storage device includes: performing a background read operation on a nonvolatile memory by using a default read voltage level; performing a read retry operation on the nonvolatile memory by using a corrected read voltage level when the background read operation fails; storing the corrected read voltage level in a history buffer when the read retry operation succeeds; and performing a host read operation on the nonvolatile memory by using the history buffer in response to a read request received from a host.