A method of operating a storage device including a non-volatile memory includes storing program and erase counts of the non-volatile memory as metadata in units of super blocks, wherein each of the super blocks includes a pre-defined number of blocks of the non-volatile memory, performing a read operation on a first block included in a first super block based on a first read level, storing the first read level as a history read level of the first super block in a history buffer when the read operation on the first block is successful, receiving a read request for a second block of the first super block and an address of the second block from a host, and performing a read operation on the second block based on the history read level stored in the history buffer. The pre-defined number is at least two.