A recovery method and apparatus for use in a redundant array of independent disks (RAID) storage device is provided that includes a plurality of nonvolatile memory devices. The recovery method includes: reading a data chunk, in which an uncorrectable error occurs, from the plurality of nonvolatile memory devices, selecting a plurality of sub-stripes including a parity and excluding the data chunk, and performing, in parallel, a first recovery operation of adjusting a read level to recover the data chunk and a second recovery operation of processing the plurality of sub-stripes to recover a sub-stripe including the data chunk. The parallel performance of the first and second recovery operations is completed according to an earlier completion of one of the first and second recovery operations.