Methods and devices for managing address mapping information may include writing address mapping recovery information on a user data area of a storage medium in an initially set size unit, the address mapping recovery information being generated in response to a write operation, storing the address mapping recovery information without being written on the storage medium in a non-volatile memory device when an abnormal power off occurs in a storage device, and updating the address mapping information related to the storage device based on the address mapping recovery information stored in the non-volatile memory device and the storage medium when power is applied to the storage device.