Provided are a portable storage device and a method of data recovery using the same, in which when the integrity of the recorded data is damaged, the integrity of the recorded data can be easily recovered. The portable storage device includes a memory unit that stores predetermined recovery information for the recorded data, a determining unit that determines whether a device that accesses the recorded data supports the stored recovery information, and a control unit that selectively recovers the recorded data using the stored recovery information based on a result of the determination.