A method of operating a storage device includes receiving a first logical address from a host, determining whether first metadata stored in a volatile memory of the storage device and associated with the first logical address is corrupted, processing the first metadata as an uncorrectable error when the first metadata is determined to be corrupted, providing an error message to the host indicating that an operation cannot be performed on data associated with the first logical address when the first metadata is processed as the uncorrectable error, after the providing of the error message, receiving a second logical address from the host, determining whether second metadata stored in the volatile memory and associated with the second logical address is corrupted, and performing an operation of accessing the non-volatile memory based on the second metadata, when the second metadata is not determined to be corrupted.