The present technology relates to an electronic device. According to the present technology, a storage device having improved original data recovery capability may include a memory device including a plurality of memory cells, and configured to perform a read operation on data stored in the plurality of memory cells according to read mode information, and to output read data associated with the read operation and a memory controller configured to receive the read data, change the read mode information when error correction decoding for the read data fails, and control the memory device to perform the read operation again according to the changed read mode information. The read mode information may include information on a data interface between the memory device and the memory controller.